P2633 Count on a tree

Given a tree with $n$ nodes, each node has a weight. There are $m$ queries. For each query, you are given $u, v, k$, and you need to answer the $k$-th smallest node weight on the path between $u \text{ xor last}$ and $v$. Here, $\text{last}$ is the answer to the previous query, initially defined as $0$, i.e., in the first query, $u$ is not xored.

The first line contains two integers $n, m$. The second line contains $n$ integers, where the $i$-th integer denotes the weight of node $i$. Each of the next $n - 1$ lines contains two integers $x, y$, indicating that there is an edge between node $x$ and node $y$. Each of the last $m$ lines contains three integers $u, v, k$, representing one query.

Output $m$ lines, each containing a positive integer, which is the answer to each query.

Constraints: For $100\%$ of the testdata, $1 \le n, m \le 10^5$, and node weights are in $[1, 2 ^ {31} - 1]$. Please refrain from brute force... Source: bzoj2588 Spoj10628. The testdata for this problem is self-made by Luogu, generated using [CYaRon](https://github.com/luogu-dev/cyaron) in 5 minutes. Translated by ChatGPT 5