Problem Description
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 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.
Input format
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 \\
eq 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 \\
eq 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 $ .
Output format
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.
Sample #1
Sample Input #1
4 4 1 2 twenty three 3 4 1 4 3 2 4 2 1 3 1 2 3 1
Sample Output #1
No
Sample #2
Sample Input #2
6 2 1 2 twenty three 3 4 2 5 5 6 1 4 2 2 6 7
Sample Output #2
Yes 4 2 4 1 6
Sample #3
Sample Input #3
6 2 1 2 twenty three 3 4 2 5 5 6 1 4 3 1 6 5
Sample Output #3
Yes 6 1 4 3 0
Prompt
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.
There is a very clever conclusion to the XOR value of the path on the tree: assuming a root, if the XOR sum from the root Node to the point \(x\) is \(v_x\), then the path \(( The XOR sum of x,y)\) is \(v_x\oplus v_y\)
Then the meaning of a restriction at this time is \(v_x\oplus v_y=a\). Transform it into \(v_x\oplus a=v_y\). At this time, you can determine whether there is a restriction through the composition of the picture. untie.
As for minimizing the XOR sum of the weights of all points. Then consider when a \(v_x\) will be counted into the total point-weighted XOR sum, if and only if the degree of \(x\) in the tree is an odd number.
Then to minimize the XOR sum at this time, you can designate a point \(a\) for each connected block of the graph above to determine whether there is a solution, then \(v of each point in the connected block \) value can be written as \(v_a\oplus w\), then if this point will be calculated into the total point weight XOR sum, the answer will definitely be more XOR or the previous \(w\),\ Whether \(v_a\) is counted will also change.
Then if No point weight of a connected block will be included in the answer at this time, then \(v_a\) can be determined casually, which will Not affect the answer. Otherwise, the sum of the XORs of all points’\(w\) can be recorded as \(s\), and a \(a\) recorded as a point weight can be assigned a value of \(s\ ), at this time the total XOR sum is 0.
// LUOGU_RID: 103370522
#include<bits/stdc + + .h>
using namespace std;
const int N=3e5 + 5;
int n,q,d[N],in[N],f[N],p[N],ans,fl,a[N],b[N];
struct graph{
int hd[N],e_num;
struct edge{
int v,nxt,w;
}e[N<<1];
void add_edge(int u,int v,int w)
{
e[ + + e_num]=(edge){v,hd[u],w};
hd[u]=e_num;
// printf("%d %d %d\\
",u,v,w);
}
}g,h;
void dfs(int x,int w,int t)
{
if(d[x]^w & amp; & amp;f[x])
{
puts("No");
exit(0);
}
if(!f[x])
{
d[x]=w,f[x]=t;
// printf("%d %d\\
",x,f[x]);
for(int i=h.hd[x];i;i=h.e[i].nxt)
{
// printf("qzmyyds:%d\\
",e[i].v);
dfs(h.e[i].v,w^h.e[i].w,t);
}
}
}
void sou(int x,int y)
{
for(int i=g.hd[x];i;i=g.e[i].nxt)
{
if(g.e[i].v^y)
sou(g.e[i].v,x);
else
b[g.e[i].w]=a[x]^a[y];
}
}
int main()
{
// memset(d,-1,sizeof(d));
scanf("%d%d", & amp;n, & amp;q);
for(int i=1;i<n; + + i)
{
int u,v;
scanf("%d%d", & amp;u, & amp;v);
g.add_edge(u,v,i);
g.add_edge(v,u,i);
+ + in[u], + + in[v];
}
while(q--)
{
int u,v,x;
scanf("%d%d%d", & amp;u, & amp;v, & amp;x);
// printf("%d\\
",x);
h.add_edge(u,v,x);
h.add_edge(v,u,x);
}
for(int i=1;i<=n;i + + )
if(!f[i])
dfs(i,0,i);
// for(int i=1;i<=n;i + + )
// printf("%d %d\\
",f[i],d[i]);
puts("Yes");
for(int i=1;i<=n;i + + )
if(in[i] &1)
p[f[i]]^=1,ans^=d[i];
// for(int i=1;i<=n;i + + )
// printf("%d ",p[i]);
// puts("") ;
p[1]=0;
for(int i=2;i<=n;i + + )
{
if(f[i]==i & amp; & amp;p[i])
p[i]=ans,ans=0;
// printf("hjhyyds:%d %d\\
",d[i],p[f[i]]);
a[i]=d[i]^p[f[i]];
}
// for(int i=1;i<=n;i + + )
// print
sou(1,0);
for(int i=1;i<n;i + + )
printf("%d ",b[i]);
return 0;
}