P13579 [CCPC 2024 重庆站] 沙堆

本题目来自仓库

给定一棵 $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,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`。