Every day each of Farmer John's N (1 <= N <= 100,000) cows conveniently numbered 1..N move from the barn to her private pasture. The pastures are organized as a tree, with the barn being on pasture 1. Exactly N-1 cow unidirectional paths connect the pastures; directly connected pastures have exactly one path. Path i connects pastures A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N).
Cow i has a private pasture P_i (1 <= P_i <= N). The barn's small
door lets only one cow exit at a time; and the patient cows wait
until their predecessor arrives at her private pasture. First cow
1 exits and moves to pasture P_1. Then cow 2 exits and goes to
pasture P_2, and so on.
While cow i walks to P_i she might or might not pass through a
pasture that already contains an eating cow. When a cow is present
in a pasture, cow i walks slower than usual to prevent annoying her
friend.
Consider the following pasture network, where the number between
parentheses indicates the pastures' owner.

        1 (3)        
       / \
  (1) 4   3 (5)
     / \   
(2) 2   5 (4)

First, cow 1 walks to her pasture:

        1 (3)        
       / \
  [1] 4*  3 (5)
     / \   
(2) 2   5 (4)

When cow 2 moves to her pasture, she first passes into the barn's
pasture, pasture 1. Then she sneaks around cow 1 in pasture 4 before
arriving at her own pasture.

        1 (3)
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

Cow 3 doesn't get far at all -- she lounges in the barn's pasture, #1.

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5 (4)

Cow 4 must slow for pasture 1 and 4 on her way to pasture 5:

        1* [3]
       / \
  [1] 4*  3 (5)
     / \   
[2] 2*  5* [4]

Cow 5 slows for cow 3 in pasture 1 and then enters her own private pasture:

        1* [3]
       / \
  [1] 4*  3*[5]
     / \   
[2] 2*  5* [4]

FJ would like to know how many times each cow has to slow down.

看中文题面点这里

* Line 1: Line 1 contains a single integer: N

* Lines 2..N: Line i+1 contains two space-separated integers: A_i and B_i

* Lines N+1..N+N: line N+i contains a single integer: P_i

* Lines 1..N: Line i contains the number of times cow i has to slow down.

5
1 4
5 4
1 3
2 4
4
2
1
5
3

0
1
0
2
1

题目分析：

树剖+线段树单点修改 区间查询

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int net[500010],head[500010],to[500010];
int val[500010],top[500010],number[500010],v[500010];
int fa[500010],size[500010],son[500010],deep[500010];
int tot,cnt;
struct your
{
    int x,y;
    int sum;
}a[500000];
void add(int x,int y)
{
    net[++tot]=head[x];
    to[tot]=y;
    head[x]=tot;
}
void dfs(int x,int temp)
{
    fa[x]=temp;
    deep[x]=deep[temp]+1;
    size[x]=1;
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==temp) continue;
        dfs(to[i],x);
        size[x]+=size[to[i]];
        if(size[son[x]]<size[to[i]]) son[x]=to[i];
    }
}
void dfs2(int x,int temp)
{
    number[x]=++cnt;
    top[x]=temp;
    val[number[x]]=v[x];
    if(son[x]) dfs2(son[x],temp);
    for(int i=head[x];i;i=net[i])
        if(to[i]!=son[x]&&to[i]!=fa[x])
            dfs2(to[i],to[i]);
}
void build(int dx,int dy,int num)
{
	a[num].x=dx,a[num].y=dy;
	if(dx==dy) return;
	int mid=(dx+dy)>>1;
	build(dx,mid,num<<1);
	build(mid+1,dy,num<<1|1);
}
void update(int dx,int c,int num)
{
	if(a[num].x==dx&&a[num].y==dx) 
	{
		a[num].sum+=c;
		return ;
	}
	int mid=(a[num].x+a[num].y)>>1;
	if(dx<=mid) update(dx,c,num<<1);
	else update(dx,c,num<<1|1);
	a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
}
int ask(int dx,int dy,int num)
{
	if(a[num].x==dx&&a[num].y==dy)
		return a[num].sum;
	int mid=(a[num].x+a[num].y)>>1;
	if(dx>mid) return ask(dx,dy,num<<1|1);
	if(dy<=mid) return ask(dx,dy,num<<1);
	return ask(dx,mid,num<<1)+ask(mid+1,dy,num<<1|1);
}
int findsum(int x)
{
	int ans=0;
	while(top[x]!=1)
	{
		ans+=ask(number[top[x]],number[x],1);
		x=fa[top[x]];
	}
	ans+=ask(1,number[x],1);
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(y,x),add(x,y);
	}
	dfs(1,0);
	dfs2(1,1);
	build(1,n,1);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",findsum(x));
		update(number[x],1,1);
	}
}