```cpp
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define D double
#define LD long double
#define LL long long
#define ULL unsigned long long
#define S string
#define fi first
#define se second
#define mp make_pair
#define id(x) (lower_bound(b + 1,b + tot + 1,a[x]) - b)
#define rid(x) (b[x])
using namespace std;
vector <int> e[100010];
int size[100010];
int top[100010];
int son[100010];
int dep[100010];
int fa[100010];
int root[100010];
int maxroot;
map<int, int> s;
int tot;
int n, m;
struct node
{
int ls;
int rs;
int sum;
} tree[100010 * 130];
int a[100010];
int b[100010];
void dfs1(int now, int f, int depp)
{
size[now] = 1;
fa[now] = f;
dep[now] = depp;
if (e[now].size() == 1)
{
return;
}
int maxx = -1;
for (auto i : e[now])
{
if (i != f)
{
dfs1(i, now, depp + 1);
size[now] += size[i];
if (size[i] > maxx)
{
son[now] = i;
maxx = size[i];
}
}
}
return;
}
void dfs2(int now, int topp)
{
top[now] = topp;
if (!son[now])
{
return;
}
dfs2(son[now], topp);
for (auto i : e[now])
{
if (i != fa[now] && i != son[now])
{
dfs2(i, i);
}
}
return;
}
int lca(int x, int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
{
swap(x, y);
}
x = fa[top[x]];
}
if (dep[x] < dep[y])
{
swap(x, y);
}
return y;
}
void build(int &rt, int l, int r)
{
rt = ++maxroot;
if (l == r)
{
tree[rt].sum = 0;
return;
}
build(tree[rt].ls, l, (l + r) / 2);
build(tree[rt].rs, (l + r) / 2 + 1, r);
return;
}
void update(int &rt, int his, int l, int r, int now)
{
rt = ++maxroot;
tree[rt] = tree[his];
tree[rt].sum++;
if (l == r)
{
return;
}
if (now <= (l + r) / 2)
{
update(tree[rt].ls, tree[his].ls, l, (l + r) / 2, now);
}
else
{
update(tree[rt].rs, tree[his].rs, (l + r) / 2 + 1, r, now);
}
return;
}
int query(int x, int y, int z, int w, int l, int r, int k)
{
if (l == r)
{
return l;
}
int lsum = tree[tree[x].ls].sum + tree[tree[y].ls].sum - tree[tree[z].ls].sum - tree[tree[w].ls].sum;
if (lsum < k)
{
return query(tree[x].rs, tree[y].rs, tree[z].rs, tree[w].rs, (l + r) / 2 + 1, r, k - lsum);
}
else
{
return query(tree[x].ls, tree[y].ls, tree[z].ls, tree[w].ls, l, (l + r) / 2, k);
}
}
void dfs(int now, int f)
{
update(root[now], root[f], 1, tot, id(now));
for (auto i : e[now])
{
if (i != f)
{
dfs(i, now);
}
}
return;
}
int main()
{
// freopen("P2633_2.in", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
tot = unique(b + 1, b + n + 1) - (b + 1);
build(root[0], 1, tot);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
// cerr << "Wathis?";
dfs1(1, 0, 1);
dfs2(1, 1);
// for (int i = 1; i <= n; i++)
// {
// cout << fa[i] << ' ';
// }
// cout << '\n';
build(root[0], 1, tot);
dfs(1, 0);
int last = 0;
int x, y, k;
while (m--)
{
cin >> x >> y >> k;
x ^= last;
last = rid(query(root[x], root[y], root[lca(x, y)], root[fa[lca(x, y)]], 1, tot, k));
cout << last << '\n';
}
return 0;
}
```
by TankYu @ 2022-10-22 20:31:38