Problem

Description

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]

Input

* 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

Output

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

Sample Input

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

Sample Output

0 
1 
0 
2 
1

HINT

无

Solution

Analysis

dfs序维护子树信息

Attention

无

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
const int N=100010;
int n;
struct Edge{
    int v,nxt;
} e[N<<1];int head[N],tot;
il void add_edge(int u,int v){
    e[++tot]=(Edge){v,head[u]};
    head[u]=tot;
}
int c[N];
int in[N],out[N],cnt;
il void dfs(int u,int fa){
    in[u]=++cnt;
    repe(i,u){
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u);
    }
    out[u]=cnt;
}
il void add(int x,int addv){
    for(;x<=n+1;x+=lowbit(x)){
        c[x]+=addv;
    }
}
il int query(int x){
    int res=0;
    for(;x>0;x-=lowbit(x)) res+=c[x];
    return res;
}
int main(){
    n=read();
    rep(i,2,n){
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,1);
    rep(i,1,n){
        int a=read();
        printf("%d\n",query(in[a]));
        add(in[a],1);
        add(out[a]+1,-1);
    }
    return 0;
}