问题描述

Snuke在古代遗址中找到了一棵具有 $N$ 个顶点的树的记录。以下是所发现的信息：

• 树的顶点编号为 $1,2,...,N$，边的编号为 $1,2,...,N-1$。
• 边 $i$ 连接了顶点 $a_i$ 和 $b_i$。
• 每条边的长度是 $1$ 到 $10^{18}$（含）之间的整数。
• 从顶点 $i$ 到顶点 $1,...,N$ 的最短距离之和为 $s_i$。

请根据以上信息恢复每条边的长度。输入保证可以根据记录一致地确定边的长度。此外，可以证明在这种情况下，每条边的长度是唯一确定的。

约束条件

• $2 \leq N \leq 10^{5}$
• $1 \leq a_i,b_i \leq N$
• $1 \leq s_i \leq 10^{18}$
• 给定的图是一棵树。
• 所有输入值都是整数。
• 可以一致地恢复边的长度。
• 在恢复后的图中，每条边的长度是 $1$ 到 $10^{18}$（含）之间的整数。

部分得分

• 在价值为 $300$ 分的测试集中，$a_i = i, b_i = i+1$。
• 在价值为 $200$ 分的测试集中，$N \geq 3, a_i = 1, b_i = i+1$。

输入

输入以以下格式从标准输入给出：

$N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $s_1$ $s_2$ $...$ $s_{N}$

输出

输出 $N-1$ 行。第 $i$ 行必须包含边 $i$ 的长度。

示例输入 1

4
1 2
2 3
3 4
8 6 6 8

示例输出 1

1
2
1

• 给定的记录对应于下图的树：

示例输入 2

5
1 2
1 3
1 4
1 5
10 13 16 19 22

示例输出 2

1
2
3
4

• 给定的记录对应于下图的树：

示例输入 3

15
9 10
9 15
15 4
4 13
13 2
13 11
2 14
13 6
11 1
1 12
12 3
12 7
2 5
14 8
1154 890 2240 883 2047 2076 1590 1104 1726 1791 1091 1226 841 1000 901

示例输出 3

5
75
2
6
7
50
10
95
9
8
78
28
89
8