2806. [ICPC 2017西安区域赛]树上异或xor

【题目描述】

There is a tree with $n$ nodes. For each node, there is an integer value $a_i$, ($1≤a_i≤1,000,000,000$ for $1≤i≤n$).

There is $q$ queries which are described as follow:

Assume the value on the path from node $a$ to node $b$ is $t_0,t_1,⋯t_m$，You are supposed to calculate $t_0\ xor\ t_k\ xor\ t_{2k}\ xor\ ...\ xor\ t_{pk} (pk≤m)$.

题目大意：

给出一棵树，每个节点有个 $val$，$q$ 个询问。

询问格式：$u$, $v$, $k$, 从 $u$ 到 $v$ 的路径， 每隔 $k$ 个点取一个，求所有点的 $val$ 值异或和。

【输入格式】

There is only $1$ dataset.($n≤50,000,q≤50,000$).

First $2$ integers $n,q$

In the first $n−1$ lines, there are two integers $u,v$, indicates there is an edge connect node $u$ and node $v$.

In the next $n$ lines, There is an integer $a_i$ ($1≤a_i≤1,000,000,000$).

In the next $q$ lines, There is three integers $a,b$ and $k$. ($1≤a,b,k≤n$).

【输出格式】

For each query, output an integer in one line, without any additional space.

【样例1输入】

5 6
1 5
4 1
2 1
3 2
19
26
0
8
17
5 5 1
1 3 2
3 2 1
5 4 2
3 4 4
1 4 5

【样例1输出】

17
19
26
25
0
19

【样例2】

点击下载样例2

【数据规模与约定】

对于 $30\%$ 的数据，$1 \leq n,q \leq 20$;

对于 $60\%$ 的数据，$1 \leq n,q \leq 1000$;

对于 $100\%$ 的数据，$1 \leq n,q \leq 50000，1≤a_i≤1,000,000,000$;

【来源】

2017 ACM-ICPC 亚洲区（西安赛区）网络赛