[USACO 2010 Feb G]Slowing down

题号：NC24727
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

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]

FJ would like to know how many times each cow has to slow down.

输入描述:

* Line 1: Line 1 contains a single integer: N
* Lines 2..N: Line i+1 contains two space-separated integers:  and 
* Lines N+1..N+N: line N+i contains a single integer:

输出描述:

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

示例1

输入

复制

输出

复制