题目描述

给定一棵包含 n 个节点的树（节点编号从 1 到 n），每个节点有一个整数权值 w[i]。
对于每个节点 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 5
2 2
12 5
4 4
5 5

数据范围

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