You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

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$。

样例

样例输入 #1

4
10 -5 -5 0
1 2
1 3
2 4

样例输出 #1

YES
2
1 2 5
1 3 5

样例解释 #1

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

1. 执行操作 $(1, 2, 5)$：节点 $1$ 是节点 $2$ 的祖先，$a_1=10 > 0$，$a_2=-5 < 0$。
   • $a_1 \leftarrow 10 - 5 = 5$
   • $a_2 \leftarrow -5 + 5 = 0$
   • 当前点权变为 $[5, 0, -5, 0]$。
2. 执行操作 $(1, 3, 5)$：节点 $1$ 是节点 $3$ 的祖先，$a_1=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$。