XOR, Tree, and Queries

题意翻译

给定一棵 $n$ 个节点的树, 编号为 $1\sim n$ , 我们需要给每条边赋一个整数值 $a_i$ , $0\leqslant a_i < 2^{30}$ . 现在有 $q$ 条限制, 每条限制形如 $u,v,x$ , 表示点 $u$ 到点 $v$ 的树上最短路径权值为 $x$ , 路径权值定义为边的异或和. 求是否有解, 如果有解, 需最小化 $a_1\oplus a_2 \oplus \dots \oplus a_{n-1}$ ,并输出 $a_1,a_2,\dots,a_{n-1}$ .

题目描述

You are given a tree of $ n $ vertices. The vertices are numbered from $ 1 $ to $ n $ . You will need to assign a weight to each edge. Let the weight of the $ i $ -th edge be $ a_i $ ( $ 1 \leq i \leq n-1 $ ). The weight of each edge should be an integer between $ 0 $ and $ 2^{30}-1 $ , inclusive. You are given $ q $ conditions. Each condition consists of three integers $ u $ , $ v $ , and $ x $ . This means that the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of all edges on the shortest path from $ u $ to $ v $ should be $ x $ . Find out if there exist $ a_1, a_2, \ldots, a_{n-1} $ that satisfy the given conditions. If yes, print a solution such that $ a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1} $ is the smallest. Here, $ \oplus $ denotes the bitwise XOR operation. If there are multiple solutions such that $ a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1} $ is the smallest, print any.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 2 \le n \le 2.5 \cdot 10^5 $ , $ 0 \le q \le 2.5 \cdot 10^5 $ ). The $ i $ -th of the following $ n-1 $ lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le n $ , $ x_i \neq y_i $ ), meaning that the $ i $ -th edge connects vertices $ x_i $ and $ y_i $ in the tree. It is guaranteed that the given edges form a tree. The following $ q $ lines contain information about conditions. Each line contains three integers $ u $ , $ v $ , $ x $ ( $ 1 \le u, v \le n $ , $ u \neq v $ , $ 0 \le x \le 2^{30}-1 $ ), meaning that the bitwise XOR of all edges on the shortest path from $ u $ to $ v $ should be $ x $ .

输出格式

If there do not exist $ a_1 $ , $ a_2 $ , ..., $ a_{n-1} $ that satisfy the given conditions, print "No". Otherwise, print "Yes" in the first line. Then print $ n-1 $ integers on the next line, where the $ i $ -th integer is the weight of the $ i $ -th edge. If there are multiple solutions that satisfy the given conditions, print a solution such that $ a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1} $ is the smallest. If there are multiple solutions such that $ a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1} $ is the smallest, print any. When printing "Yes" or "No", you can print each letter in any case (either upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

输入输出样例

输入样例 #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

说明

For the first example, there does not exist a set of edge weights that satisfies the given conditions. For the second example, the two given conditions are $ a_1 \oplus a_2 \oplus a_3=2 $ and $ a_4 \oplus a_5=7 $ . There can be multiple solutions, for example, $ (a_1, a_2, a_3, a_4, a_5)=(1, 2, 1, 4, 3) $ . For the third example, the two given conditions are $ a_1 \oplus a_2 \oplus a_3=3 $ and $ a_1 \oplus a_4 \oplus a_5=5 $ . There are multiple solutions that satisfy the given conditions. $ (a_1, a_2, a_3, a_4, a_5)=(1, 1, 3, 4, 0) $ satisfies the given conditions, but the bitwise XOR of all edge weights is $ 7 $ , which does not have the smallest $ a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1} $ , so it cannot be the answer.

题目大意：
给定一棵有n个节点的树，节点编号为1到n。需要给每条边赋予一个整数值a_i，范围在0到2^30-1之间。有q条限制，每条限制包含三个整数u、v和x，表示从u到v的树上最短路径的边权异或和应为x。要求判断是否存在满足给定条件的a_1,a_2,...,a_{n-1}。如果存在，则输出满足条件的最小的a_1⊕a_2⊕...⊕a_{n-1}的解，如果有多个解，则输出任意一个。

输入输出数据格式：
输入格式：
- 第一行包含两个整数n和q，分别表示节点数和限制数。
- 接下来的n-1行，每行包含两个整数x_i和y_i，表示第i条边连接的节点。
- 接下来的q行，每行包含三个整数u、v和x，表示一条限制条件。

输出格式：
- 如果不存在满足条件的解，则输出"No"。
- 如果存在满足条件的解，则第一行输出"Yes"，第二行输出n-1个整数，表示每条边的权值。如果有多个解，输出任意一个使得a_1⊕a_2⊕...⊕a_{n-1}最小的解。题目大意： 给定一棵有n个节点的树，节点编号为1到n。需要给每条边赋予一个整数值a_i，范围在0到2^30-1之间。有q条限制，每条限制包含三个整数u、v和x，表示从u到v的树上最短路径的边权异或和应为x。要求判断是否存在满足给定条件的a_1,a_2,...,a_{n-1}。如果存在，则输出满足条件的最小的a_1⊕a_2⊕...⊕a_{n-1}的解，如果有多个解，则输出任意一个。 输入输出数据格式： 输入格式： - 第一行包含两个整数n和q，分别表示节点数和限制数。 - 接下来的n-1行，每行包含两个整数x_i和y_i，表示第i条边连接的节点。 - 接下来的q行，每行包含三个整数u、v和x，表示一条限制条件。 输出格式： - 如果不存在满足条件的解，则输出"No"。 - 如果存在满足条件的解，则第一行输出"Yes"，第二行输出n-1个整数，表示每条边的权值。如果有多个解，输出任意一个使得a_1⊕a_2⊕...⊕a_{n-1}最小的解。