P8201 [ChuanZhi Cup #4 Finals] [yLOI2021] Living on a Tree (hard version)

**This problem is the harder version of P8200, and the solutions to the two problems are slightly different. The difference in the statement between this problem and P8200 is that this problem gives node weights on the tree, rather than edge weights.** Xiao Zhi lives in “ChuanZhi Kingdom”, a country with $n$ cities, where the cities are connected by $n-1$ roads. Each city has a wealth index $w_i$. We define the cost for Xiao Zhi to travel from city $a$ to city $b$ as $\mathrm{dis}_{a, b} = \bigoplus \limits_{u \in \mathrm{path}\left(a, b\right)} w_u$, where $\bigoplus$ denotes **bitwise XOR** (if you do not know what **bitwise XOR** is, please refer to the hints/explanations below), and $\mathrm{path}\left(a,b\right)$ denotes the set of nodes on the simple path from $a$ to $b$ (including $a$ and $b$). That is, $\mathrm{dis}_{a, b}$ means: after listing all nodes on the simple path from $a$ to $b$ as $u_1, u_2, u_3, \dots$, compute $w_{u_1} \bigoplus w_{u_2}\bigoplus w_{u_3} \dots$. One day, Xiao Zhi got the chance to participate in the ChuanZhi Cup. On his way to the contest venue, he thought of a problem, but it seems he cannot solve it, so he told you this problem. Smart classmate, can you help him?

Xiao Zhi said: “Since our country has only $n$ cities and $n-1$ roads, then our country is equivalent to a tree. I am thinking: in our country, does there exist a city such that ‘the XOR of the cost to city $a$ and the cost to city $b$ equals $k$’? It is so hard, I cannot figure it out. Can you help me?” That is, given cities $a, b$ and an integer $k$, please determine whether there exists a city $t$ such that $\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} = k$.

The first line contains two integers $n$, $m$, denoting the number of cities and the number of queries. The second line contains $n$ integers $w_i$, denoting the wealth index of city $i$. The next $n-1$ lines each contain two integers $x, y$, indicating that there is an edge connecting city $x$ and city $y$. The next $m$ lines each contain three integers $a, b, k$, indicating that Xiao Zhi travels from city $a$ to city $b$, and the meaning of $k$ is the same as in the description.

Output a total of $m$ lines. For the $i$-th query, if there exists at least one city $t$ that satisfies the requirement, output `Yes`. If there is no city that satisfies the condition, output `No`. The output is case-insensitive. For example, `Yes`, `yES`, `YES`, `yes`, etc. are all accepted as `Yes`.

### Explanation of related concepts “Tree”: A tree is an undirected simple connected graph with $n$ nodes and $n-1$ edges. “Bitwise XOR”: Bitwise XOR is a binary operation. Compare the binary bits of two numbers bit by bit: the same gives $0$, different gives $1$. For example, $3 \bigoplus 5 = (011)_2 \bigoplus (101)_2 = (110)_2 = 6$. ### Explanation of Sample 1 The figure below shows the map of ChuanZhi Kingdom. $\forall t \in \{1, 2, 3, 4, 5\}$, it is impossible to have $\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} = 4$ and $\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 12$, so output `No`. If we take $t=4$, then $\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 10$, so output `Yes`.  ### Constraints For all test points, it is guaranteed that $1 < n \leq 5 \times 10^5$, $1 \leq m \leq 5 \times 10^5$, $0 \leq w_i \leq 1\times 10^7$. For each query, it is guaranteed that $1 \leq a,b \leq n$ and $a \neq b$, $0 \leq k \leq 1\times 10^7$. ### Notes - Please pay attention to the impact of constant factors on program efficiency. - For two numbers $x, y \leq 10^7$, $x \bigoplus y$ may be greater than $10^7$. Please pay special attention to this. Translated by ChatGPT 5