← 返回题目列表

Codeforces · 1615/D

D. X(或)-mas 树

中文机器翻译题面 查看原题

'那是圣诞节前一天晚上,圣诞老人正在疯狂地布置他的新圣诞树!树中有 $$$n$$$ 个节点,由 $$$n-1$$$ 边连接。在树的每条边上,都有一组圣诞灯,可以用二进制表示的整数来表示。

他让 $$$m$$$ 精灵过来欣赏他的树。每个精灵都被分配了两个节点,$$$a$$$ 和 $$$b$$$,并且该精灵查看两个节点之间的简单路径上的所有灯光。此后,精灵最喜欢的数字将成为该路径边缘上的灯光值的按位异或。

然而,北极已经从一场严重的流感中恢复过来。因此,圣诞老人忘记了他在树上放的一些灯的配置,他已经离开了北极!幸运的是,精灵们前来救援,每个精灵都告诉圣诞老人他被分配了哪一对节点 $$$(a_i, b_i)$$$,以及他最喜欢的数字中设置位数的奇偶性。换句话说,当他最喜欢的数字用二进制写成时,他记得$$$1$$$的数量是奇数还是偶数。

帮助圣诞老人确定记忆是否可能一致,如果是,记住他的树是什么样子,也许你会载入史册!

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。

每个测试用例的第一行包含两个整数,$$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq m \leq 2 \cdot 10^5$$$) — 分别是树的大小和精灵的数量。

每个测试用例接下来的 $$$n-1$$$ 行均包含三个整数:$$$x$$$、$$$y$$$ 和 $$$v$$$ ($$$1 \leq x, y \leq n$$$; $$$-1 \leq v < 2^{30}$$$) - 意味着节点 $$$x$$$ 和 $$$x$$$ 之间有一条边$$$y$$$。如果

- $$$v = -1$$$:圣诞老人不记得这条边缘的灯组是什么。
- $$$v \geq 0$$$:边缘上的一组灯是 $$$v$$$。

每个测试用例接下来的 $$$m$$$ 行各包含三个整数,$$$a$$$、$$$b$$$ 和 $$$p$$$ ($$$1 \leq a, b \leq n$$$; $$$a \neq b$$$; $$$0 \leq p \leq 1$$$) - 精灵被分配到的节点,以及精灵最喜欢的数字中设置位数的奇偶校验。

保证所有 $$$n$$$ 的总和以及所有 $$$m$$$ 的总和各不超过 $$$2 \cdot 10^5$$$。

保证给定的边形成一棵树。

输出

对于每个测试用例,首先打印 YES 或 NO(在任何情况下),无论是否有一棵树与圣诞老人的记忆一致。

如果答案为“是”,则打印 $$$n-1$$$ 行,每行包含三个整数:$$$x$$$、$$$y$$$ 和 $$$v$$$ ($$$1 \le x, y \le n$$$; $$$0 \le v < 2^{30}$$$) — 边和该边上的整数。边的集合必须与输入中的相同,并且如果先前指定了某些边的值,则它不能更改。您可以按任何顺序打印边缘。

如果有多个答案,请打印其中一个。

示例

输入 #1

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

输出 #1

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

注意

第一个测试用例是语句中的图像。

一种可能的答案是将边 $$$(1, 2)$$$ 的值分配给 $$$5$$$,将边 $$$(2, 5)$$$ 的值分配给 $$$3$$$。这是正确的,因为:

- 第一个精灵从节点 $$$2$$$ 到节点 $$$3$$$。这个精灵最喜欢的数字是 $$$4$$$,因此他记住了值 $$$1$$$(因为 $$$4$$$ 在其二进制表示中具有奇数个 $$$1$$$ 位)。
- 第二个精灵从节点 $$$2$$$ 到节点 $$$5$$$。这个精灵最喜欢的数字是 $$$3$$$,所以他记住了值 $$$0$$$(因为 $$$3$$$ 在其二进制表示中具有偶数个 $$$1$$$ 位)。
- 第三个精灵从节点 $$$5$$$ 到节点 $$$6$$$。这个精灵最喜欢的数字是 $$$7$$$,所以他记住了值 $$$1$$$(因为 $$$7$$$ 在其二进制表示中具有奇数个 $$$1$$$ 位)。
- 第四个精灵从节点 $$$6$$$ 到节点 $$$1$$$。这个精灵最喜欢的数字是 $$$1$$$,因此他记住了值 $$$1$$$(因为 $$$1$$$ 在其二进制表示中具有奇数个 $$$1$$$ 位)。
- 第五个精灵从节点 $$$4$$$ 到节点 $$$5$$$。这个精灵最喜欢的数字是$$$4$$$,所以他记住了数字$$$1$$$(因为$$$4$$$在其二进制表示中具有奇数个$$$1$$$位)。

请注意,还有其他可能的答案。