Problem
There is a tree with n nodes. For each node, there is an integer value a_iai, (1 \le a_i \le 1,000,000,0001≤ai≤1,000,000,000 for 1 \le i \le n1≤i≤n). There is qq queries which are described as follow: Assume the value on the path from node a to node b is t_0, t_1, \cdots t_mt0,t1,⋯tm. You are supposed to calculate t_0 xor t_k xor t_{2k} xor ... xor t_{pk} (pk \le m)(pk≤m).
Input Format
There are multi datasets. (\sum n \le 50,000, \sum q \le 500,000)(∑n≤50,000,∑q≤500,000).
For each dataset: In the first n-1n−1 lines, there are two integers u,vu,v, indicates there is an edge connect node uuand node vv.
In the next nn lines, There is an integer a_iai (1 \le a_i \le 1,000,000,0001≤ai≤1,000,000,000).
In the next qq lines, There is three integers a,ba,b and kk. (1 \le a,b,k \le n1≤a,b,k≤n).
Output Format
For each query, output an integer in one line, without any additional space.
样例输入
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
样例输出
17 19 26 25 0 19
代码如下：
1 //https://nanti.jisuanke.com/t/A1273 《Xor》
2 #include <iostream>
3 #include <algorithm>
4 #include <cstdio>
5 #include <cstring>
6 using namespace std;
7 const int N = 5e4 + 5;
8 int fa[N][20], deep[N], head[N];
9 int v[N], cnt;
10 bool vis[N];
11 int dp[N][105];
12 struct data
13 {
14 int to, next;
15 }e[2 * N];
16
17 void insert(int u, int v)
18 {
19 e[++cnt].to = v;
20 e[cnt].next = head[u];
21 head[u] = cnt;
22 e[++cnt].to = u;
23 e[cnt].next = head[v];
24 head[v] = cnt;
25 }
26 int cal(int x, int t)
27 {
28 for (int i = 0; i <= 19; i++)
29 if (t&(1 << i)) x = fa[x][i];
30 return x;
31 }
32 void dfs(int x)
33 {
34 vis[x] = 1;
35 for (int i = 1; i <= 19; i++)
36 {
37 if (deep[x]<(1 << i))break;
38 fa[x][i] = fa[fa[x][i - 1]][i - 1];///倍增处理祖先信息
39 }
40 for (int k = 1; k <= 100; k++)
41 {
42 dp[x][k] = v[x];
43 if (deep[x]<k) continue;
44 int p = cal(x, k);
45 dp[x][k] ^= dp[p][k];
46 }
47 for (int i = head[x]; i; i = e[i].next)
48 {
49 if (vis[e[i].to]) continue;
50 deep[e[i].to] = deep[x] + 1;
51 fa[e[i].to][0] = x;
52 dfs(e[i].to);
53 }
54 }
55 int lca(int x, int y)///求lca
56 {
57 if (deep[x]<deep[y]) swap(x, y);
58 x = cal(x, deep[x] - deep[y]);
59 for (int i = 19; i >= 0; i--)
60 if (fa[x][i] != fa[y][i])
61 {
62 x = fa[x][i];
63 y = fa[y][i];
64 }
65 if (x == y)return x;
66 else return fa[x][0];
67 }
68
69 void init()
70 {
71 cnt = 0;
72 memset(head, 0, sizeof(head));
73 memset(vis, 0, sizeof(vis));
74 memset(dp, 0, sizeof(dp));
75 memset(deep, 0, sizeof(deep));
76 memset(fa,0,sizeof(fa));
77 }
78
79 int main()
80 {
81 int n, q;
82 while (scanf("%d%d", &n, &q) != EOF)
83 {
84 init();
85 for (int i = 1; i<n; i++)
86 {
87 int x, y; scanf("%d%d", &x, &y);
88 insert(x, y);
89 }
90 for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
91 dfs(1);
92 while (q--)
93 {
94 int x, y, k; scanf("%d%d%d", &x, &y, &k);
95 int pa = lca(x, y);
96 if (k <= 100)
97 {
98 int ans = dp[x][k];
99 int h = (deep[x] - deep[pa]) % k;
100 int t = k - h;
101 if (deep[pa] >= t)
102 {
103 int l = cal(pa, t);
104 ans ^= dp[l][k];
105 }
106 int r = k - h;
107 t = deep[y] - deep[pa] - r;
108 if (t<0) goto endw2;
109 t %= k;
110 y = cal(y, t);///
111 ans ^= dp[y][k];
112 t = k - r;
113 if (deep[pa] >= t)
114 {
115 int l = cal(pa, t);
116 ans ^= dp[l][k];
117 }
118 endw2:;
119 printf("%d\n", ans);
120 }
121 else
122 {
123 int ans = 0;
124 while (1)
125 {
126 ans ^= v[x];
127 if (deep[x] - k<deep[pa]) break;
128 x = cal(x, k);
129 }
130 int l = k - (deep[x] - deep[pa]);
131 int t = deep[y] - deep[pa] - l;
132 if (t<0) goto endw;
133 t %= k;
134 y = cal(y, t);
135 while (1)
136 {
137 ans ^= v[y];
138 if (deep[y] - k <= deep[pa]) break;
139 y = cal(y, k);
140 }
141 endw:;
142 printf("%d\n", ans);
143 }
144 }
145 }
146 return 0;
147 }
148 /**
149 8 11
150 1 2
151 2 3
152 2 4
153 1 5
154 5 6
155 5 7
156 4 8
157 3 5 6 2 7 0 1 10
158 1 8 1
159 answer=14
160 */