当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7027:0 tree

Special Judge 特殊评判
题目描述
We have a tree $\langle V,E\rangle$ consists of $n$ vertices with weight $a_i (i \in V)$ on the vertices and weight $b_e (e=\langle u,v\rangle \in E)$ on the bidirectional edges. $a_i$ is a non-negative integer and $b_e$ is an integer.

You can perform no more than $4n$ following operations:

For the shortest path from $x$ to $y$ traveling $k+1$ vertices $(v_0,v_1,v_2,...,v_k)$ where $v_0 = x ,v_k = y$, let $e_i=\langle v_{i},v_{i+1}\rangle (0 \leq i < k)$. In one operation, you can choose $2$ vertices $x,y$ and a non-negative integer $w$, to make:
$$a_x \leftarrow a_x \bigoplus w;\quad a_y \leftarrow a_y \bigoplus w;\quad b_{e_i}\leftarrow b_{e_i} + (-1) ^ i w \, (0 \leq i < k)$$
Where $\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,b_{e}$ equal to $0$. If it is possible, output a solution using no more than $4n$ operations described above.
输入解释
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 following 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 line contains three integers $x_j,y_j,w_j(1 \leq x_j,y_j \leq n,-10^9 \leq w_j \leq 10^9)$, representing an edge between vertices $x_j,y_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'' in the first line if you can make all $a_i,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.

The first line contains one integer $k$ - the number of operations you make.

Then $k$ lines follow, each line contains $3$ integers $X_j,Y_j,W_j(1 \leq X_j, Y_j \leq n,0 \leq W_j \leq 10^{14})$, representing one operation.

If there are multiple possible solutions, output any.
输入样例
3
1
0
2
2 3
1 2 -2
3
5 4 1
1 2 -5
2 3 -5
输出样例
YES
0
NO
YES
3
1 3 5
2 3 7
2 3 3

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-7027

最后修改于 2021-10-23T19:11:06+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
3000/3000MS(Java/Others) 524288/524288K(Java/Others)