P2982 [USACO10FEB] Slowing down G
题目描述
每天，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$ 在穿过该牧场时会比平时走得更慢，以避免打扰她的朋友。
```cpp
考虑以下牧场网络，其中括号中的数字表示牧场的主人。
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$ 需要放慢速度的次数。
说明/提示
数据范围：$1 \leq A_i, B_i, P_i \leq N \leq 10^5$。