P8965 Falling into Dream | Falling into Dream

The gods toy with the mortal world. So-called fate is nothing more than a die thrown by the gods. The butterfly that the flower cannot wait for eventually becomes a strange dream, restarting again and again. The gods’ puppets are strangled time after time; in the name of love, they vanish into the sea of flowers of time. Behind countless obsessions, there is always a twisted “truth”. What you promised never appeared. Sleepless all night, perhaps I was just being self-willed, loving this human world once on your behalf. “The most devout only pray; only the undevout have demands.” There was never faith; by risking one’s life to save someone, one was fortunate enough to reach heaven.

Given an unrooted tree with $n$ nodes, each edge has a non-negative integer weight. The nodes are numbered from $1$ to $n$. For each pair of nodes $(x, y)$, define the distance $\operatorname{dis}(x, y)$ as the XOR sum of edge weights on the unique simple path between $x$ and $y$. Given two nodes $x, y$, define the value of node $i$ as the XOR of the distances from $x$ to $i$ and from $y$ to $i$, i.e., $$ \operatorname{val}_{x, y}(i) = \operatorname{dis}(x, i) \oplus \operatorname{dis}(y, i) \textsf{。} $$ Now there are $q$ queries. Each query gives four integers $x, y, l, r$. You need to compute $\displaystyle \bigoplus_{i = l}^{r} \operatorname{val}_{x, y}(i)$, i.e., compute $$ \operatorname{val}_{x, y}(l) \oplus \operatorname{val}_{x, y}(l + 1) \oplus \cdots \oplus \operatorname{val}_{x, y}(r - 1) \oplus \operatorname{val}_{x, y}(r) \textsf{。} $$ In the formulas above, $\oplus$ denotes the bitwise XOR operator.

The first line contains two integers $n, q$. The next $n - 1$ lines each contain three integers $u, v, w$, indicating that there is an edge of weight $w$ between $u$ and $v$. The next $q$ lines each contain four integers $x, y, l, r$, indicating one query.

Output $q$ lines, each containing one integer, the answer to the corresponding query.

**Sample Explanation**  The tree given by the input is shown in the figure above. For distances between pairs of nodes, we have: - $\operatorname{dis}(1, 1) = \operatorname{dis}(1, 3) = \operatorname{dis}(2, 2) = \operatorname{dis}(3, 1) = \operatorname{dis}(3, 3) = 0$, and - $\operatorname{dis}(1, 2) = \operatorname{dis}(2, 1) = \operatorname{dis}(2, 3) = \operatorname{dis}(3, 2) = 1$. Query $1$: $\operatorname{val}_{1, 2}(1) \oplus \operatorname{val}_{1, 2}(2) \oplus \operatorname{val}_{1, 2}(3) = (0 \oplus 1) \oplus (1 \oplus 0) \oplus (0 \oplus 1) = 1 \oplus 1 \oplus 1 = 1$. Query $2$: $\operatorname{val}_{2, 3}(2) \oplus \operatorname{val}_{2, 3}(3) = (0 \oplus 1) \oplus (1 \oplus 0) = 1 \oplus 1 = 0$. --- **Constraints** **This problem uses bundled testdata.** | Subtask ID | $n \le$ | $q \le$ | Score | | :----------: | :----------: | :----------: | :----------: | | 1 | $100$ | $10$ | 24 | | 2 | $10^6$ | $10$ | 14 | | 3 | $100$ | $10^6$ | 14 | | 4 | $10^6$ | $10^6$ | 48 | For $100\%$ of the data, it is guaranteed that $1 \le n, q \le {10}^6$, $1 \le u, v, x, y \le n$, $1 \le l \le r \le n$, and $0 \le w < 2^{31}$. --- **Hint** The maximum I/O size of this problem reaches 60 MiB. Please pay attention to I/O efficiency. Translated by ChatGPT 5