CF1788F.XOR, Tree, and Queries
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 ai ( 1≤i≤n−1 ). The weight of each edge should be an integer between 0 and 230−1 , inclusive.
You are given q conditions. Each condition consists of three integers u , v , and x . This means that the bitwise XOR of all edges on the shortest path from u to v should be x .
Find out if there exist a1,a2,…,an−1 that satisfy the given conditions. If yes, print a solution such that a1⊕a2⊕…⊕an−1 is the smallest. Here, ⊕ denotes the bitwise XOR operation.
If there are multiple solutions such that a1⊕a2⊕…⊕an−1 is the smallest, print any.
输入格式
The first line contains two integers n and q ( 2≤n≤2.5⋅105 , 0≤q≤2.5⋅105 ).
The i -th of the following n−1 lines contains two integers xi and yi ( 1≤xi,yi≤n , xi=yi ), meaning that the i -th edge connects vertices xi and yi 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≤u,v≤n , u=v , 0≤x≤230−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 a1 , a2 , ..., an−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 a1⊕a2⊕…⊕an−1 is the smallest.
If there are multiple solutions such that a1⊕a2⊕…⊕an−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 a1⊕a2⊕a3=2 and a4⊕a5=7 . There can be multiple solutions, for example, (a1,a2,a3,a4,a5)=(1,2,1,4,3) .
For the third example, the two given conditions are a1⊕a2⊕a3=3 and a1⊕a4⊕a5=5 . There are multiple solutions that satisfy the given conditions.
(a1,a2,a3,a4,a5)=(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 a1⊕a2⊕…⊕an−1 , so it cannot be the answer.