XOR, Tree, and Queries
Contest: Codeforces Round 851 (Div. 2)
Difficulty rating: 2500
Tags: bitmasks, constructive algorithms, dfs and similar, dsu, graphs, greedy, implementation, trees

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 \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$$$.

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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4 4
1 2
2 3
3 4
1 4 3
2 4 2
1 3 1
2 3 1

Example output:
No

Example input:
6 2
1 2
2 3
3 4
2 5
5 6
1 4 2
2 6 7

Example output:
Yes
4 2 4 1 6

Editorial:
Let's denote $$$p_i$$$ as xor of edges in path from node $$$1$$$ to node $$$i$$$. Edges in path from $$$i$$$ to $$$j$$$ is
(edges in path from $$$1$$$ to $$$i$$$) + (edges in path from $$$1$$$ to $$$j$$$) — $$$2 \times $$$(edges in path from $$$1$$$ to $$$lca(i, j)$$$)
where $$$lca(i, j)$$$ denotes the least common ancestor of $$$i$$$ and $$$j$$$. Since xor of two same number is $$$0$$$, we can observe that xor of path from $$$i$$$ to $$$j$$$ is $$$p_i \oplus p_j$$$.
If we know every $$$p_i$$$ for all $$$i$$$, weight of edge connecting $$$i$$$ and $$$j$$$ is $$$p_i \oplus p_j$$$, so deciding weight of every edge is equivalent to deciding every $$$p_i$$$ for $$$i \geq 2$$$.
Let $$$G$$$ be the original tree graph. Let's make a undirected weighted graph $$$G'$$$ from the given condition. Condition ($$$u$$$, $$$v$$$, $$$x$$$) makes an edge connecting $$$u$$$ and $$$v$$$ with weight $$$x$$$. This edge means that $$$p_v=p_u \oplus x$$$. Now if $$$u$$$ and $$$v$$$ are connected by edges in $$$G'$$$, this means that $$$p_v=p_u \oplus $$$ (xor of edges in path from $$$u$$$ to $$$v$$$).
First, let's check if it is possible to make a graph that satisfies the conditions.
If $$$G'$$$ is a connected graph, we can solve $$$p_i$$$ using dfs from node $$$1$$$. For edges not used in dfs (back edges), we have to check if it is valid with the solved $$$p_i$$$. Specifically, if there is an edge ($$$u$$$, $$$v$$$, $$$x$$$), we need to check if $$$p_u \oplus p_v=x$$$.
Now let's think when $$$G'$$$ is not a connected graph. By dividing the graph into connected components, we can solve if it is impossible to make a graph that satisfies the conditions in a same fashion.
Now let's try to minimize $$$a_1 \oplus a_2 \oplus \cdots \oplus a_{n-1}$$$.
For edge $$$(u, v)$$$ in $$$G$$$, weight of edge is $$$p_u \oplus p_v$$$. By substituting $$$a_i$$$ into $$$p_{x_i} \oplus$$$ $$$p_{y_i}$$$, $$$a_1 \oplus a_2 \oplus \cdots \oplus a_{n-1}$$$ can be written as xor of $$$p_i$$$ where node $$$i$$$ has odd degree. Let the connected components of $$$G'$$$ be $$$G_1, G_2, \ldots, G_k$$$. Pick any vertex $$$r_k$$$ in each component $$$G_k$$$. For every vertex $$$i$$$ in $$$G_k$$$, $$$p_i$$$ is expressed as $$$p_{r_k} \oplus $$$ (xor of edges in path from $$$r_k$$$ to $$$i$$$).
Let's define a set $$$L$$$ as $$$L= $$${$$$i | G_i$$$ has odd number of odd degree vertices}.
By substituting $$$p_i$$$ into ($$$p_{r_k} \oplus$$$ (xor of edges in path in $$$G'$$$ from $$$r_k$$$ to $$$i$$$)), we can rewrite "xor of $$$p_i$$$ where node $$$i$$$ has odd degree" into $$$\bigoplus_{k \in L} p_{r_k} \oplus c$$$ where $$$c$$$ is a constant.
If $$$L$$$ is empty, the answer is constant and any solution that satisfy the given conditions will be the answer.
If $$$L$$$ is not empty, set one of $$$p_{r_k}$$$ to $$$c$$$ and other $$$p_{r_k}$$$ as $$$0$$$ so that $$$a_1 \oplus a_2 \oplus \cdots a_{n-1}$$$ is $$$0$$$.
We can solve the problem in $$$O(N)$$$.
Fast $$$O(NlogX)$$$ solution might be accepted, including the solution where you divide the weight of edge by bits.