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 4ドルn$ 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.

제한

힌트