[USACO10FEB]Slowing down G

题目描述

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. ```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 <= N <= 100000,编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树,粮仓在1号牧场。恰好有N-1条道路直接连接着牧场,使得牧场之间都恰好有一条路径相连。第i条路连接着A\_i,B\_i,(1 <= A\_i <= N; 1 <= B\_i <= N)。 奶牛们每人有一个私人牧场P\_i (1 <= P\_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开,前往P\_1;然后是奶牛2,以此类推。 当奶牛i走向牧场P\_i时候,他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时,奶牛i会放慢自己的速度,防止打扰他的朋友。 FJ想要知道奶牛们总共要放慢多少次速度。

输入输出格式

输入格式


\* 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.

输入输出样例

输入样例 #1

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

输出样例 #1

0 
1 
0 
2 
1