树到云端
题号：NC293975
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}“或停留在金色枝头声声歌唱”。
\hspace{15pt}给定一棵边权为 1，由 n 个节点构成的树，第 i 个点的点权为 {\rm val}_i ，设 {\rm dis}(i,j) 表示点 i 到点 j 的最短距离（特别地，{\rm dis}(i,i)=0 ），记 t_i=\sum\limits_{j=1}^n {\rm val}_j\times {\rm dis}(i,j)。

\hspace{15pt}现在给定树的结构和 t 数组，要求求出 {\rm val} 数组（数据保证 {\rm val}_i 均为正整数）。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(2\le n\le 6\times 10^5\right)
\hspace{15pt}此后 n-1 行，第 i 行输入两个整数 u_i,v_i \left(1\le u_i,v_i\le n\right) 表示第 i 条树边连接节点 u_i 和节点 v_i。
\hspace{15pt}第 n+1 行输入 n 个整数 t_1, t_2, \dots, t_n \left(1\le t_i\le 10^9\right) 代表给定的数组。

n\\<br />u_1\ v_1\\<br />u_2\ v_2\\<br />\vdots\\<br />u_{n-1}\ v_{n-1}\\<br />t_1\ t_2\ t_3\dots\ t_n

输出描述:

\hspace{15pt}在一行上输出 n 个正整数 val_1, val_2, \dots, val_n，第 i 个整数表示节点 i 的点权。
示例1

输入

复制 
2
1 2
1 3

输出

复制 
3 1
示例2

输入

复制 
5
1 2
1 3
1 4
1 5
18 40 40 24 28

输出

复制 
6 1 1 9 7
示例3

输入

复制 
5
1 2
1 3
3 4
4 5
34 40 34 40 56

输出

复制 
3 9 3 5 4