第 K 大？主席树！
考虑树上静态求路径信息（具有区间减法性质）：
\(s_x + s_y - s_{lca} - s_{fa_{lca}}\)，其中 \(s_x\) 表示结点 \(x\) 到根的信息。
那么扩展到主席树即可。
注意离散化！
注意重复元素！我就是因为这一点在 BZOJ RE，SPOJ 原题 WA 的，不过洛谷数据没有重复的。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' | ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}
const int N = 1e5;
long long lastans;
int n,m,rt[N + 10],len;
long long a[N + 10],ind[N + 10];
int to[(N << 1) + 10],pre[(N << 1) + 10],first[N + 10];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v;
pre[tot] = first[u];
first[u] = tot;
}
struct segnode
{
int cnt,lson,rson;
} seg[(N << 5) + 10];
int insert(int x,int tl,int tr,int p)
{
static int tot = 0;
int cur = ++tot;
seg[cur] = seg[p];
if(tl == tr)
{
++cnt(cur);
return cur;
}
int mid = tl + tr >> 1;
if(x <= mid)
ls(cur) = insert(x,tl,mid,ls(cur));
else
rs(cur) = insert(x,mid + 1,tr,rs(cur));
cnt(cur) = cnt(ls(cur)) + cnt(rs(cur));
return cur;
}
int query(int k,int tl,int tr,int x,int y,int lca,int fa_lca)
{
if(tl == tr)
return tl;
int mid = tl + tr >> 1;
int cnt = cnt(ls(x)) + cnt(ls(y)) - cnt(ls(lca)) - cnt(ls(fa_lca));
if(k <= cnt)
return query(k,tl,mid,ls(x),ls(y),ls(lca),ls(fa_lca));
else
return query(k - cnt,mid + 1,tr,rs(x),rs(y),rs(lca),rs(fa_lca));
}
int fa[N + 10],dep[N + 10],sz[N + 10],son[N + 10],top[N + 10];
int q[N + 10],head,tail;
inline int getlca(int x,int y)
{
while(top[x] ^ top[y])
dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return dep[x] < dep[y] ? x : y;
}
int main()
{
read(n),read(m);
for(register int i = 1;i <= n;++i)
read(a[i]),ind[i] = a[i];
sort(ind + 1,ind + n + 1);
len = unique(ind + 1,ind + n + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
int u,v;
for(register int i = 1;i < n;++i)
read(u),read(v),add(u,v),add(v,u);
rt[1] = insert(a[1],1,n,0);
q[++tail] = dep[1] = 1;
while(head < tail)
{
int p = q[++head];
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p;
dep[to[i]] = dep[p] + 1;
rt[to[i]] = insert(a[to[i]],1,n,rt[p]);
q[++tail] = to[i];
}
}
for(register int i = n;i;--i)
{
sz[fa[q[i]]] += sz[q[i]];
if(!son[fa[q[i]]] || sz[q[i]] > sz[son[fa[q[i]]]])
son[fa[q[i]]] = q[i];
}
for(register int i = 1;i <= n;++i)
top[q[i]] = son[fa[q[i]]] == q[i] ? top[fa[q[i]]] : q[i];
int x,y,k,lca;
while(m--)
{
read(x),read(y),read(k);
x ^= lastans;
lca = getlca(x,y);
printf("%lld\n",lastans = ind[query(k,1,n,rt[x],rt[y],rt[lca],rt[fa[lca]])]);
}
return 0;
}