题目描述

给出一棵有 $N$ 个点 $N-1$ 条无向边的无根树。

一开始有 $N$ 头牛聚集在点1排队准备出发去到各自的目的地 $P_i$。首先奶牛 $1$ 离开，前往 $P_1$；然后是奶牛 $2$，以此类推。

每头牛到达各自 目的地 后就开始休息。

统计每头牛在到达目的地之前路过多少个有牛在休息的点。

输入格式

第一行一个整数 $N(1 \le N \le 10^5)$。

下来 $N-1$ 对整数 $x \ y$，每对整数表示一条无向边。

下来 $N$ 个整数 $P_i$。

输出格式

第 $1 \sim N$ 行：第 $i$ 行包括奶牛 $i$ 在到达目的地之前路过多少个有牛在休息的点。。

输入输出样例 #1

输入 #1

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

输出 #1

0 
1 
0 
2 
1

提示

 样例的牧场结构如下：（括号内的数字代表了牧场的所有者）

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

首先，牛1 从点1直接到达点4，牛1路过点1和点4，这两个点都没有牛在休息。

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

牛2 从点1 到 点4 再到点2，点4有牛在休息

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

牛3直接到点1（没动）

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

牛4路过 点1 点4 点5，其中点1 和 点4都有牛在休息

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

牛5 路过点1和点3，其中点1有牛在休息

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