题目类型：主席树+\(LCA\)
传送门：>Here<
题意：给出一棵树。每个节点有点权。问某一条路径上排名第\(K\)小的点权是多少
解题思路
类似区间第\(K\)小，但放在了树上。
考虑维护一棵主席树，其中每棵权值线段树维护从一个节点\(i\)到根节点上每个点权的出现次数（点权先离散化）。于是我们可以
得到\((u,v)\)之间的路径上，某一权值的出现次数为$$sum[u]+sum[v]-sum[lca]-sum[fa[lca]]$$于是就很简单了
那么我们要按照什么顺序来进行\(update\)呢？由于我们要维护的是\(u\)到根节点上的所有点，如果想像正常主席树一样在另一个主
席树的基础上进行单点更新，那么这个点只能是它的父亲。于是我们要以\(dfs\)的顺序进行更新。
Code
/*By DennyQi 2018*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100010;
const int MAXM = 200010;
const int INF = 1061109567;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
int x = 0; int w = 1; register char c = getchar();
for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());
if(c == '-') w = -1, c = getchar();
for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;
}
struct Num{
int val,rnk,idx;
}a[MAXN];
int N,M,x,y,k,lastans,lca;
int first[MAXM],nxt[MAXM],to[MAXM],cnt;
int dep[MAXN],f[MAXN][25],T[MAXN],mp[MAXN];
struct zxs{
int ls[MAXN<<5],rs[MAXN<<5],sum[MAXN<<5],numNode;
int update(int pre, int l, int r, int x){
int cur = ++numNode;
ls[cur] = ls[pre], rs[cur] = rs[pre], sum[cur] = sum[pre] + 1;
if(l<r){
int mid = (l+r)/2;
if(x <= mid) ls[cur] = update(ls[pre], l, mid, x);
else rs[cur] = update(rs[pre], mid+1, r, x);
}
return cur;
}
int query(int u, int v, int lca, int flca, int l, int r, int k){
int amt = sum[ls[u]]+sum[ls[v]]-sum[ls[lca]]-sum[ls[flca]];
if(l>=r) return mp[l];
int mid = (l+r)/2;
if(amt >= k) return query(ls[u],ls[v],ls[lca],ls[flca],l,mid,k);
else return query(rs[u],rs[v],rs[lca],rs[flca],mid+1,r,k-amt);
}
}qxz;
inline bool cmp1(const Num& a, const Num& b){ return a.val < b.val; }
inline bool cmp2(const Num& a, const Num& b){ return a.idx < b.idx; }
inline void add(int u, int v){
to[++cnt]=v, nxt[cnt]=first[u], first[u]=cnt;
}
void lca_dfs(int u, int Fa, int d){
dep[u] = d;
f[u][0] = Fa;
for(int i = 1; (1 << i) <= d; ++i){
f[u][i] = f[f[u][i-1]][i-1];
}
int v;
for(int i = first[u]; i; i = nxt[i]){
if((v = to[i]) == Fa) continue;
T[v] = qxz.update(T[u], 1, N, a[v].rnk);
lca_dfs(v, u, d+1);
}
}
inline int getLca(int a, int b){
if(dep[a] < dep[b]) swap(a, b);
for(int i = 20; i >= 0; --i){
if(dep[a] - (1<<i) < dep[b]) continue;
a = f[a][i];
}
if(a == b) return a;
for(int i = 20; i >= 0; --i){
if(f[a][i] == f[b][i]) continue;
a = f[a][i], b = f[b][i];
}
return f[a][0];
}
int main(){
// freopen(".in","r",stdin);
N = read(), M = read();
for(int i = 1; i <= N; ++i){
a[i].val = read();
a[i].idx = i;
}
sort(a+1, a+N+1, cmp1);
for(int i = 1; i <= N; ++i){
if(i != 1 && a[i].val == a[i-1].val) a[i].rnk = a[i-1].rnk;
else a[i].rnk = i;
}
sort(a+1, a+N+1, cmp2);
for(int i = 1; i <= N; ++i) mp[a[i].rnk] = a[i].val;
for(int i = 1; i < N; ++i){
x = read(), y = read();
add(x, y);
add(y, x);
}
T[1] = qxz.update(0, 1, N, a[1].rnk);
lca_dfs(1, 0, 1);
for(int i = 1; i <= M; ++i){
x = read(), y = read(), k = read();
x = x ^ lastans;
lca = getLca(x, y);
lastans = qxz.query(T[x],T[y],T[lca],T[f[lca][0]],1,N,k);
printf("%d\n", lastans);
}
return 0;
}