题目类型：主席树+\(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;

}