分数: 800 点
问题陈述
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第行必须包含 Edge 的长度 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