P6177 [Template] Tree Block Decomposition / Count on a tree II

Originally bzoj2589.

Given a tree with $n$ nodes, each node has an integer value. The value on node $i$ is $val_i$. There are $m$ queries. Each query gives $u', v$. You need to decrypt them to get $u, v$, and then ask: how many distinct integers are on the path from $u$ to $v$. Decryption method: $u = u' \operatorname{xor} lastans$. Here, $lastans$ is the answer to the previous query. If there is no previous query, it is $0$.

The first line contains two integers $n$ and $m$. The second line contains $n$ integers. The $i$-th integer represents $val_i$. In the next $n - 1$ lines, each line contains two integers $u, v$, describing an edge. In the next $m$ lines, each line contains two integers $u', v$, describing a query.

For each query, output one integer per line, which is the answer.

For $100\%$ of the testdata, $1 \le u, v \le n \le 4 \times 10^4$, $1 \le m \le 10^5$, $0 \le u', val_i < 2^{31}$。 Translated by ChatGPT 5