← 返回题目列表

AtCoder · asaporo2_d

D. 古树记录

中文机器翻译题面 查看原题

分数: 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
  • 给定的记录对应于如下所示的树:
010664dd33d69063a99075c0f7a391f8.png

示例输入 2

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

示例输出 2

1
2
3
4
  • 给定的记录对应于如下所示的树:
41891e0c5dc01850fd29636b200f7f49.png

示例输入 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