23150번 - 0 Tree 스페셜 저지다국어

We have a tree $\langle V, E \rangle$ that consists of $n$ vertices numbered from $1$ to $n$. Each vertex $i \in V$ has weight $a_i$. Each bidirectional edge $e = \langle u, v \rangle \in E$ has weight $b_e$. Here, $a_i$ are non-negative integers, and $b_e$ are integers.

You can perform at most $4 n$ operations. For each operation, select two vertices $X$ and $Y$, and a non-negative integer $W$. Consider the shortest path from $X$ to $Y$ (a path is shortest if the number of edges $k$ in it is minimum possible). Let this path consist of $k + 1$ vertices $(v_0, v_1, v_2, \ldots, v_k)$ where $v_0 = X$, $v_k = Y$, and for $0 \leq i < k$, the edges $e_i = \langle v_{i}, v_{i+1} \rangle \in E$. The operation changes the weights as follows:

$$a_X \leftarrow a_X \bigoplus W\text{;} \quad a_Y \leftarrow a_Y \bigoplus W\text{;} \quad b_{e_i}\leftarrow b_{e_i} + (-1)^i \cdot W \text{ for } 0 \leq i < k\text{.}$$

Here, $\bigoplus$ denotes the bitwise XOR operation. We can notice that, if $X = Y$, nothing will change.

You need to decide whether it is possible to make all $a_i$ and all $b_e$ equal to $0$. If it is possible, find a way to do so.

The first line contains an integer $T$ ($1 \leq T \leq 250$), the number of test cases. Then $T$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^4$), the number of vertices.

The second line contains $n$ non-negative integers $a_i$ ($0 \leq a_i < 2^{30}$), the weight on each vertex.

Then $n - 1$ lines follow, each of them contains three integers $u_j$, $v_j$, $w_j$ ($1 \leq u_j, v_j \leq n$, $-10^9 \leq w_j \leq 10^9$), representing an edge between vertices $u_j$ and $v_j$ with weight $w_j$. It is guaranteed that the given edges form a tree.

It is guaranteed that $\sum n \leq 10^5$.

For each test case, output "YES" on the first line if you can make all $a_i$ and all $b_{e}$ equal to $0$ with no more than $4n$ operations. Output "NO" otherwise.

If you can make all weights equal to $0$, output your solution in the following $k + 1$ ($0 \leq k \leq 4n$) lines as follows.

On the next line, print an integer $k$: the number of operations you make.

Then print $k$ lines, each line containing three integers $X$, $Y$, and $W$ ($1 \leq X, Y \leq n$, $0 \leq W \leq 10^{14}$), representing one operation.

If there are several possible solutions, print any one of them.