样例下载

【题目描述】

农夫约翰有 $N$ 个农场，编号为 $1$ ~ $N$ ，编号为 $i$ 的农场中住着 $X_i$ 头奶牛。农场间有若干条双向通行的道路，每条道路的长度均为 $1$。任意两个农场间存在着唯一的路径。

现在约翰准备选择一个农场，让奶牛们来参加聚会。奶牛们是很懒的，她们去往某个农场总是走行程最短的路径。由于奶牛的产奶量和她的运动量之间存在着联系，约翰计算出了任意一个农场作为聚会地点时所有奶牛的行走路程数据。具体地，如果在编号为 $i$ 的农场聚会，则所有奶牛到达农场 $i$ 行走的路程之和为 $S_i$。

约翰经过计算，得到了 $S_i$。但是他却把每个农场住着的奶牛数量 $X_i$ 忘记了。

请你根据约翰计算得到的 $S_i$ 的值反推出 $X_i$ 的值。如果有多组解，输出任意一组即可。如果无解，则输出 -1 。

【输入格式】

第一行：一个整数 $N$

接下来 $N-1$ 行，每行两个整数 $u, v$ 表示农场 $u$ 和农场 $v$ 之间有一条道路。

第 $N+1$ 行：共 $N$ 个整数，依次表示 $S_1, S_2, …, S_N$。

【输出格式】

一行：如果有解，则输出 $N$ 个整数，依次表示 $X_1, X_2, …, X_N$；如果无解，则输出 -1 。

【样例1输入】

3
1 2
1 3
1 4 2

【样例1输出】

2 0 1

【样例2输入】

3
1 2
1 3
1 2 3

【样例2输出】

-1

【数据范围】

$1 ≤ N ≤ 5×10^5, 0 ≤ S_i ≤ 2×10^9$