题目描述

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

输入格式
第一行两个整数N,M。

第二行有N个整数，其中第i个整数表示点i的权值。

后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。

最后M行每行两个整数(u,v,k)，表示一组询问。

输出格式
M行，表示每个询问的答案。

输入输出样例
输入 #1复制
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2
输出 #1复制
2
8
9
105
7
说明/提示
HINT：

N,M<=100000

第k大，比较明显的主席树，但是是树上两点的问题。

我们可以想到，主席树是一个权值线段树的前缀和，所以我们可以利用树上差分+树上前缀和来解决这个问题。

如果会树上差分+主席树，那么就是一个sb题

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,q,a[N],b[N],cnt,f[N][20],lg[N],rt[N],h[N],res;
int head[N],nex[N<<1],to[N<<1],tot;
struct node{int l,r,sum;}t[N*20];
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void change(int l,int r,int &x,int y,int k){
	x=++cnt; t[x]=t[y]; t[x].sum++;
	if(l==r)	return ;	int mid=l+r>>1;
	if(k<=mid)	change(l,mid,t[x].l,t[y].l,k);
	else	change(mid+1,r,t[x].r,t[y].r,k);
}
int ask(int l,int r,int s1,int s2,int s3,int s4,int k){
	if(l==r)	return l;	int mid=l+r>>1;
	int s=t[t[s1].l].sum+t[t[s2].l].sum-t[t[s3].l].sum-t[t[s4].l].sum;
	if(s>=k)	return ask(l,mid,t[s1].l,t[s2].l,t[s3].l,t[s4].l,k);
	else	return ask(mid+1,r,t[s1].r,t[s2].r,t[s3].r,t[s4].r,k-s);
}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	change(1,m,rt[x],rt[fa],a[x]);
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		dfs(to[i],x);
	}
}
int lca(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+1+n);	m=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)	a[i]=lower_bound(b+1,b+1+m,a[i])-b;
	for(int i=1;i<n;i++){
		int u,v;	scanf("%d %d",&u,&v);	add(u,v);	add(v,u);
	}
	dfs(1,0);
	while(q--){
		int u,v,k;	scanf("%d %d %d",&u,&v,&k);	u^=res; int fa=lca(u,v);
		res=b[ask(1,m,rt[u],rt[v],rt[fa],rt[f[fa][0]],k)];
		printf("%d\n",res);
	}
	return 0;
}