题目描述

给定一棵包含 n 个节点的树（节点编号从 1 到 n），每个节点有一个整数权值 v[i]。
请你计算 每个节点的子树和。
对于节点 u，它的子树包含 u 本身以及 u 的所有后代节点（即以 u 为根的子树中的所有节点）。
节点 u 的子树和定义为该子树中所有节点权值的总和。

输入描述

第一行一个整数 n，表示树的节点个数。
接下来 n-1 行，每行两个整数 u, v，表示树中有一条连接 u 和 v 的无向边。
最后一行包含 n 个整数，第 i 个整数表示节点 i 的权值 w[i]。

输出描述

输出一行，包含 n 个整数，第 i 个整数表示节点 i 的子树和。
数字之间用单个空格隔开。

输入样例

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

输出样例

15 2 12 4 5

数据范围

• 1 ≤ n ≤ 1000
• -10^4 ≤ w[i] ≤ 10^4
• 保证给定的图是一棵树。