P13997 【MX-X19-T6】「FeOI Round 4.5」Hug

[Hug - MIMI / Kagamine Len / MORE MORE JUMP!](https://www.bilibili.com/video/BV1du4y177qY) > 人間なんだから今日くらいは俯いたっていいじゃんか

**The overall time limit for this problem is long, and submitting too many times may trigger the daily submission limit on Luogu. Please plan your submissions accordingly.** Shizuku gives you a tree with $n$ nodes, numbered $1 \sim n$. The $i$-th node has a weight $a_i$. She asks you $q$ queries. Each query provides two nodes $x, y$. Let $p_i$ be the $i$-th node on the path from $x$ to $y$ (indexing starts from $0$). You need to compute: $$ \bigoplus_{i = 0}^{\mathrm{dis}(x, y)} (a_{p_i} + i) $$ Here, $\mathrm{dis}(x, y)$ is the number of edges on the path from $x$ to $y$, and $\oplus$ denotes the bitwise XOR operation.

The first line contains two positive integers $n, q$. The second line contains $n$ non-negative integers $a_1, \ldots, a_n$. The next $n - 1$ lines each contain two positive integers $u, v$, indicating an edge between $u$ and $v$ in the tree. The next $q$ lines each contain two positive integers $x, y$, representing a query.

Output $q$ lines. The $i$-th line should contain a non-negative integer, which is the answer to the $i$-th query.

**【Sample Explanation #1】** For the first query in sample one, $p = (3, 1, 2, 4)$. The answer is $(a_3 + 0) \oplus (a_1 + 1) \oplus (a_2 + 2) \oplus (a_4 + 3) = 0 \oplus 3 \oplus 6 \oplus 8 = 13$. For the second query in sample one, $p = (1, 2, 5)$. The answer is $(a_1 + 0) \oplus (a_2 + 1) \oplus (a_5 + 2) = 2 \oplus 5 \oplus 3 = 4$. **【Data Range】** **This problem uses bundled testing.** | Subtask ID | $n,q \leq$ | Special Properties | Score | | :-: | :-: | :-: | :-: | | $1$ | $10^3$ | None | $7$ | | $2$ | $5 \times 10^4$ | $a_i=0$ | $9$ | | $3$ | $5 \times 10^4$ | $a_i$ is a multiple of $2^{12}$ | $17$ | | $4$ | $5 \times 10^4$ | The tree is randomly generated$^\dagger$ | $5$ | | $5$ | $2 \times 10^5$ | The tree is a chain | $16$ | | $6$ | $5 \times 10^4$ | None | $19$ | | $7$ | $2 \times 10^5$ | None | $27$ | $\dagger$: The random generation method: for each $u$ from $2$ to $n$, uniformly randomly select an integer $v$ from $[1, u - 1]$, and add an edge between $u$ and $v$. Finally, the node labels are randomly shuffled. For all test cases, $1 \le n,q \le 2 \times 10^5$, $1 \le x, y \le n$, $0 \le a_i \le n$. The given edges are guaranteed to form a tree. *Translated by DeepSeek V3.1*