P2982 [USACO10FEB] Slowing down G

Every day each of Farmer John's N $(1 \le N \le 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 \le A_i \le N,1 \le B_i \le N)$. Cow $i$ has a private pasture $P_i(1 \le P_i \le 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. ```cpp 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. 每天 Farmer John 的 $N$ 头奶牛，编号 $1 \ldots N$，从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在 $1$ 号牧场。恰好有 $N-1$ 条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第 $i$ 条路连接着 $A_i$ 和 $B_i$。奶牛们每人有一个私人牧场 $P_i$。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛 $1$ 离开，前往 $P_1$；然后是奶牛 $2$，以此类推。 当奶牛 $i$ 走向牧场 $P_i$ 的时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛 $i$ 会放慢自己的速度，防止打扰他的朋友。 FJ 想要知道奶牛们总共要放慢多少次速度。

无

无

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