题目背景

本题目来自仓库 https://github.com/Disposrestfully/CCPC-CQ-2024/tree/main

题目描述

给定一棵 $n$ 个点的无向树。初始每个点 $i \ (1 \le i \le n)$ 有点权 $c_i$。考察如下操作：

• 设 $\text{deg}_x$ 为点 $x$ 的度数。若存在一个点 $x$ 满足 $c_x \ge \text{deg}_x$，则选择任意一个满足该条件的点 $x$，将 $c_x$ 减去 $\text{deg}_x$ 并将 $x$ 的所有邻居的权值加 $1$。

称一个点权序列 $(c'_1,\cdots,c'_n)$ 为终态当且仅当以上操作无法进行，即所有点 $y$ 均满足 $c'_y < \text{deg}_y$。

可以证明，对于任意无向树和点权序列，只有以下两种可能的情况：

1. 无论如何操作，在有限次操作之后都会得到终态，且任意操作均会得到同一个终态。
2. 无论如何操作，都无法在有限次操作后得到终态。

你需要判断给定的初始状态属于以上哪一种情况。如果属于第一种情况，则你需要给出任意进行操作能够得到的唯一的终态。

输入格式

输入的第一行包含一个正整数 $n \ (1\le n\le 10^6)$ 表示树的点数。

接下来 $n-1$ 行每行两个整数 $x,y \ (1 \le x,y \le n)$ 表示树的一条边。

接下来一行 $n$ 个整数 $c_i \ (0\le c_i\le 10^9)$ 表示初始点权。

输出格式

如果在有限次操作内无法到达终态，输出 -1，否则输出一行 $n$ 个整数，依次描述终态每个点的点权。

6
1 2
2 3
2 4
1 5
4 6
1 1 0 0 1 1

1 2 0 1 0 0

12
1 2
1 3
2 4
3 5
5 6
2 7
7 8
4 9
8 10
5 11
3 12
2 0 0 0 1 0 1 0 1 1 0 1

0 1 2 1 1 0 1 1 0 0 0 0

40
1 2
2 3
1 4
3 5
5 6
6 7
4 8
6 9
8 10
6 11
6 12
9 13
10 14
7 15
9 16
15 17
15 18
12 19
18 20
16 21
18 22
22 23
5 24
22 25
2 26
24 27
14 28
27 29
20 30
29 31
30 32
20 33
26 34
26 35
19 36
11 37
34 38
37 39
29 40
3 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 3 0 1 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 2 1

1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 1 0 2 1 1 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0

提示

考察以下操作序列：

• 对 $6$ 进行操作，得到点权序列 $(1,1,0,1,1,0)$；
• 对 $5$ 进行操作，得到点权序列 $(2,1,0,1,0,0)$；
• 对 $1$ 进行操作，得到点权序列 $(0,2,0,1,1,0)$；
• 对 $5$ 进行操作，得到点权序列 $(1,2,0,1,0,0)$。

而点权序列 $(1,2,0,1,0,0)$ 是终态，故输出 1 2 0 1 0 0。