P4592 [TJOI2018] XOR

There is a tree with $n$ nodes, rooted at $1$, with nodes numbered from $1$ to $n$. Each node $i$ has a value $v_i$. There are $q$ operations as follows: - $1~x~z$: Query the maximum value of $v \oplus z$ among nodes in the subtree of node $x$. - $2~x~y~z$: Query the maximum value of $v \oplus z$ among nodes on the simple path from node $x$ to node $y$.

The first line contains two integers $n$ and $q$, representing the number of nodes and the number of queries. The second line contains $n$ integers, where the $i$-th integer is the value $v_i$ of node $i$. Each of the next $n-1$ lines contains two integers $u, v$, indicating that there is an edge connecting $u$ and $v$. Each of the next $q$ lines starts with an integer $op$, indicating the type of operation. - If $op = 1$, then it is followed by two integers $x, z$, representing a query for the maximum value of $v \oplus z$ among nodes in the subtree of node $x$. - If $op = 2$, then it is followed by three integers $x, y, z$, representing a query for the maximum value of $v \oplus z$ among nodes on the simple path from node $x$ to node $y$.

For each query, output a single integer on one line representing the answer.

Constraints - For $10\%$ of the testdata, $n, q \leq 10^2$. - For $20\%$ of the testdata, $n, q \leq 10^3$. - For $40\%$ of the testdata, $n, q \leq 10^4$. - For $100\%$ of the testdata, $2 \leq n, q \leq 10^5$, $1 \leq u, v, x, y \leq n$, $1 \leq op \leq 2$, $1 \leq v_i, z \lt 2^{30}$. Translated by ChatGPT 5