← 返回题目列表

Codeforces · 1788/F

F. 异或、树和查询

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

给你一棵有 $$$n$$$ 个顶点的树。顶点编号从 $$$1$$$ 到 $$$n$$$。

您需要为每条边分配一个权重。令第 $$$i$$$ 条边的权重为 $$$a_i$$$ ($$$1 \leq i \leq n-1$$$)。每条边的权重应为 $$$0$$$ 和 $$$2^{30}-1$$$(含)之间的整数。

你有$$$q$$$条件。每个条件由三个整数 $$$u$$$、$$$v$$$ 和 $$$x$$$ 组成。这意味着从 $$$u$$$ 到 $$$v$$$ 的最短路径上的所有边的按位异或应该是 $$$x$$$。

找出是否存在满足给定条件的$$$a_1, a_2, \ldots, a_{n-1}$$$。如果是,则打印一个解决方案,使得 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ 是最小的。这里,$$$\oplus$$$表示按位异或运算。

如果存在多个解使得 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ 是最小的,则打印其中任意一个。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 2.5 \cdot 10^5$$$, $$$0 \le q \le 2.5 \cdot 10^5$$$)。

以下 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \neq y_i$$$),表示第 $$$i$$$ 条边连接顶点$$$x_i$$$ 和 $$$y_i$$$ 在树中。

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

以下 $$$q$$$ 行包含有关条件的信息。

每行包含三个整数 $$$u$$$, $$$v$$$, $$$x$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$, $$$0 \le x \le 2^{30}-1$$$),表示从 $$$u$$$ 到 $$$u$$$ 的最短路径上的所有边按位异或$$$v$$$ 应该是$$$x$$$。

输出

如果不存在满足给定条件的$$$a_1$$$, $$$a_2$$$, ..., $$$a_{n-1}$$$,则打印“No”。

否则,在第一行打印“Yes”。

然后在下一行打印 $$$n-1$$$ 个整数,其中第 $$$i$$$ 个整数是第 $$$i$$$ 个边的权重。如果有多个满足给定条件的解,则打印一个解,使得 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ 是最小的。

如果存在多个解使得 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ 是最小的,则打印其中任意一个。

打印“是”或“否”时,可以以任何大小写(大写或小写)打印每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

4 4
1 2
2 3
3 4
1 4 3
2 4 2
1 3 1
2 3 1

输出 #1

No

输入 #2

6 2
1 2
2 3
3 4
2 5
5 6
1 4 2
2 6 7

输出 #2

Yes
4 2 4 1 6

输入 #3

6 2
1 2
2 3
3 4
2 5
5 6
1 4 3
1 6 5

输出 #3

Yes
6 1 4 3 0

注意

对于第一个示例,不存在满足给定条件的边权重集。

对于第二个示例,两个给定条件是 $$$a_1 \oplus a_2 \oplus a_3=2$$$ 和 $$$a_4 \oplus a_5=7$$$。可以有多个解,例如$$$(a_1, a_2, a_3, a_4, a_5)=(1, 2, 1, 4, 3)$$$。

对于第三个示例,两个给定条件是 $$$a_1 \oplus a_2 \oplus a_3=3$$$ 和 $$$a_1 \oplus a_4 \oplus a_5=5$$$。满足给定条件的解有多种。

$$$(a_1, a_2, a_3, a_4, a_5)=(1, 1, 3, 4, 0)$$$满足给定条件,但所有边权值按位异或为$$$7$$$,不存在最小 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$,所以它不可能是答案。