14 人解决，19 人已尝试。
14 份提交通过，共有 53 份提交。
5.4 EMB 奖励。
3440. 不见了的人口数据 (Hard)
单点时限: 3.0 sec
内存限制: 256 MB
星光镇的地图是有 $n$ 个点，$n-1$ 条路，这些点从 $1$ 到 $n$ 编号，两两之间都可达；这 $n-1$ 条路的长度都是 $1$。
这 $n$ 个点是居民聚居点，第 $i$ 个点上有 $a_i$ 个居民。去年的时候，星光镇政府曾经做了个人口普查，他们投入了大量的资金，获知了所有节点的 $a_i$，而获知的目的，就是为新政府大楼的选址做准备的。由于新政府大楼一定会建在一个居民聚居点上，所以星光镇政府求出了对于每个聚居点 $j$ 的「政府大楼收益评估函数」：
$$p_j=\sum_{i=1}^n \mathrm{dis}(i,j) \cdot a_i$$
其中 $\mathrm{dis}(i,j)$ 是 $i,j$ 号点之间的最短距离。特别的，$\mathrm{dis}(i,i)=0$。
新政府大楼造好了，政府自然而然地进行了一些证据销毁工作，同时「一不小心」销毁了重金得来的人口普查数据：也就是说 $a_i$ 都丢失了。但是巧的是，所有的收益评估函数值 $p_1, p_2, \ldots, p_n$ 竟然都留存了下来。星光镇数据研究所唐纳德博士表示：「从这些函数值中，我们完全可以将所有的人口数据都反求出来。」但是唐纳德博士，虽然是一个著名的数学天才，但却很有可能是一个假博士，他这话自然不能当真。所以当星光镇政府又要造一个新的政府大楼，又要用到这些人口数据时，他们花费了巨资进行再调查。
身在异国的你听到此事后大笑不止，利用 $p_1, p_2, \ldots, p_n$ 轻轻松松地求出了 $a_1, a_2, a_3, \ldots, a_n$。
输入格式
输入具有如下形式：
$n \
u_1 \ v_1 \
\vdots \
u_{n-1} \ v_{n-1} \
p_1 \ p_2 \ \ldots \ p_{n-1} \ p_n$
第一行一个整数 $n$。
接下来 $n-1$ 行，每行两个整数 $u_i, v_i$ ($1 \le u_i,v_i \le n$)，分别表示这 $n-1$ 条路。这 $n-1$ 条路都可以双向通行。两个居民聚居点之间不会有多条路相连，也不会有一条路的两端连接了同一个居民聚居点。
最后一行，用空格隔开的 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示收益评估函数。
数据保证答案有解，并且满足 $0 \le a_1,a_2,\ldots,a_n \le 1~000$。
数据规模约定：
- 对于 Easy 档：$1 \le n \le 100$。
- 对于 Hard 档：$1 \le n \le 250~000$。
输出格式
依次序输出 $a_1, a_2, \ldots, a_n$。如果有多解，输出任意解。
样例
Input
2 1 2 11 9
Output
9 11
Input
6 1 2 1 3 3 4 3 5 5 6 32 45 19 28 16 21
Output
0 1 2 3 4 5