#P12203. X(or)-mas Tree
X(or)-mas Tree
题目链接
题意
已知一棵有 个节点的树,每条边上一个权值,现在一些边上的权值确定,一些不确定。
有 个形如 x y p
约束条件,表示节点 到 链上所有边的权值的异或和在二进制下有奇数或者偶数个一, 表示有奇数个, 表示有偶数个。
问是否存在一种方法,使得将所有不确定的边上的权值赋值后使得这棵树满足所有约束条件。
输入格式
第一行一个数 ,数据组数。
接下来每组数据,第一行两个数 。
接下来 行,每行三个数 ,表示一条连接 和 的边,如果 ,表示这条边的边权不确定,否则,边权为 。
输出格式
对于每组数据,如果有解,输出一行 YES
,否则输出 NO
。
如果有解,接下来输出 行,每行输出三个数 ,表示你的方案中连接 的边边权为 。
样例
4
6 5
1 2 -1
1 3 1
4 2 7
6 3 0
2 5 -1
2 3 1
2 5 0
5 6 1
6 1 1
4 5 1
5 3
1 2 -1
1 3 -1
1 4 1
4 5 -1
2 4 0
3 4 1
2 3 1
3 3
1 2 -1
1 3 -1
1 2 0
1 3 1
2 3 0
2 1
1 2 1
1 2 0
YES
1 2 0
1 3 1
2 4 7
3 6 0
2 5 0
YES
1 2 1
1 3 0
1 4 1
4 5 1
NO
NO