← 返回题目列表

Codeforces · 1844/G

G. 树的重量

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

给你一棵树,其中 $$$n$$$ 节点标记为 $$$1,2,\dots,n$$$。第 $$$i$$$ 条边连接节点 $$$u_i$$$ 和 $$$v_i$$$,并且具有未知的正整数权重 $$$w_i$$$。为了帮助您计算出这些权重,还给出了所有 $$$1 \le i \le n-1$$$ 的节点 $$$i$$$ 和 $$$i+1$$$ 之间的距离 $$$d_i$$$(树中节点 $$$i$$$ 和 $$$i+1$$$ 之间的简单路径上边的权重总和)。

求每条边的权重。如果有多个解决方案,请打印其中任何一个。如果没有与信息一致的权重$$$w_i$$$,则打印单个整数$$$-1$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。

接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$)。

最后一行包含 $$$n-1$$$ 整数 $$$d_1,\dots,d_{n-1}$$$ ($$$1 \le d_i \le 10^{12}$$$)。

保证给定的边形成一棵树。

输出

如果没有解决方案,则打印单个整数 $$$-1$$$。否则,输出包含权重 $$$w_1,\dots,w_{n-1}$$$ 的 $$$n-1$$$ 行。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5
1 2
1 3
2 4
2 5
31 41 59 26

输出 #1

31
10
18
8

输入 #2

3
1 2
1 3
18 18

输出 #2

-1

输入 #3

9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 2
236 205 72 125 178 216 214 117

输出 #3

31
41
59
26
53
58
97
93

注意

在第一个示例中,树如下:

在第二个示例中,请注意 $$$w_2$$$ 不允许为 $$$0$$$,因为它必须是正整数,因此无解。

在第三个示例中,树如下: