题目描述

每天，Farmer John 的 $N$ $(1 \le N \le 100{,}000)$ 头奶牛（方便地编号为 $1..N$）都会从牛棚走向各自的私人牧场。牧场形成一棵树，其中牛棚位于牧场 $1$。恰好有 $N-1$ 条无向路径连接这些牧场；直接相连的牧场之间恰好有一条路径。路径 $i$ 连接牧场 $A_i$ 和 $B_i$ $(1 \le A_i \le N, 1 \le B_i \le N)$。

奶牛 $i$ 拥有一个私人牧场 $P_i$ $(1 \le P_i \le N)$。牛棚的小门一次只能让一头奶牛出去，耐心的奶牛们会等待前一头奶牛到达她的私人牧场。首先，奶牛 $1$ 离开并走向牧场 $P_1$。接着奶牛 $2$ 离开并前往牧场 $P_2$，依此类推。

当奶牛 $i$ 走向 $P_i$ 时，她可能会经过已经有奶牛在进食的牧场。当一头奶牛出现在某个牧场时，奶牛 $i$ 在穿过该牧场时会比平时走得更慢，以避免打扰她的朋友。

考虑以下牧场网络，其中括号中的数字表示牧场的主人。

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

首先，奶牛 1 走向她的牧场：

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

当奶牛 2 走向她的牧场时，她首先进入牛棚的牧场，即牧场 1。
然后她绕过牧场 4 中的奶牛 1，最终到达自己的牧场。

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

奶牛 3 根本没走远——她在牛棚的牧场 #1 里闲逛。

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

奶牛 4 在前往牧场 5 的路上，必须在牧场 1 和 4 放慢速度：

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

奶牛 5 因为在牧场 1 遇到奶牛 3 而放慢速度，然后进入自己的私人牧场：

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

FJ 想知道每头奶牛需要放慢多少次速度。

输入格式

• 第 1 行：一个整数 $N$。
• 第 $2..N$ 行：第 $i+1$ 行包含两个以空格分隔的整数 $A_i$ 和 $B_i$。
• 第 $N+1..N+N$ 行：第 $N+i$ 行包含一个整数 $P_i$。

输出格式

• 第 $1..N$ 行：第 $i$ 行包含奶牛 $i$ 需要放慢速度的次数。

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

0 
1 
0 
2 
1 

提示

数据范围：$1 \leq A_i, B_i, P_i \leq N \leq 10^5$。