[R33D]树加减 - 代码源竞赛平台

时空限制

1S/512M

给定一棵包含 $n$ 个节点的有根树，根节点为 $1$ 。每个节点 $i$ 都有一个整数点权 $a_i$ 。

你可以执行下面操作不超过 $n$ 次：

选择两个节点 $u$ 和 $v$ ，其中 $u$ 必须是 $v$ 的祖先且 $u$ 的点权为正 ( $a_u > 0$ )， $v$ 的点权为负 ( $a_v < 0$ )。
选择一个正值 $x$ ( $1 \leq x \leq a_u$ )，并更新点权： $a_u \leftarrow a_u - x$ ， $a_v \leftarrow a_v + x$ （即 $a_u$ 减去 $x$ ， $a_v$ 加上 $x$ ）。

你的任务是判断是否存在一系列操作，使得所有节点的点权都变为 $0$ 。

如果存在，输出 YES，并给出一种具体的操作方案。注意：你给出的操作次数不能超过 $n$ 。

如果不存在，输出 NO。

第一行包含一个整数 $n$ ，表示节点的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示每个节点的初始点权。

接下来 $n-1$ 行，每行包含两个整数 $u, v$ ，表示树上的一条边。

如果无解，输出一行 NO。

如果有解，则第一行输出 YES，接下来输出你的操作方案：

首先输出一个整数 $k$ ，表示你的总操作次数。

接下来 $k$ 行，每行输出三个整数 $u, v, x$ ，表示一次操作。变量的具体意义见题目描述。

你需要保证操作次数 $k \le n$ 且每次的 $x$ 均满足 $x \leq a_u$ 。

初始点权为 $[10, -5, -5, 0]$ 。

执行操作 $(1, 2, 5)$ $(1, 2, 5)$ ：节点 $1$ $1$ 是节点 $2$ $2$ 的祖先， $a_1=10 > 0$ $a_{1} = 10 > 0$ ， $a_2=-5 < 0$ $a_{2} = - 5 < 0$ 。
- $a_1 \leftarrow 10 - 5 = 5$
- $a_2 \leftarrow -5 + 5 = 0$
- 当前点权变为 $[5, 0, -5, 0]$ 。
执行操作 $(1, 3, 5)$ $(1, 3, 5)$ ：节点 $1$ $1$ 是节点 $3$ $3$ 的祖先， $a_1=5 > 0$ $a_{1} = 5 > 0$ ， $a_3=-5 < 0$ $a_{3} = - 5 < 0$ 。
- $a_1 \leftarrow 5 - 5 = 0$
- $a_3 \leftarrow -5 + 5 = 0$
- 当前点权变为 $[0, 0, 0, 0]$ 。

所有点权都变为 $0$ ，且操作次数为 $2$ ，不超过 $n=4$ 。这是一个合法的方案。

对于 $40\%$ 的数据， $1 \leq n \leq 1000$ 。

对于 $100\%$ 的数据， $1 \leq n \leq 2 \times 10^5$ ， $-10^9 \leq a_i \leq 10^9$ ，保证 $\sum_{i=1}^{n} a_i = 0$ 。