P2633

赏 $8$ 个关注。

除了第 $6$ 个点 AC 全 RE。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=7e5+5;
int n,m,a[N],b[N],root[N],sz;
vector<int>e[N];
int dep[N],siz[N],fa[N],son[N];
int dfs(int u,int father){
	dep[u]=dep[father]+1;
	fa[u]=father;
	siz[u]=1;
	int maxn=-1;
	for (auto v:e[u]){
		if (v==father) continue;
		int sizes=dfs(v,u);
		siz[u]+=sizes;
		if (sizes>maxn) maxn=sizes,son[u]=v;
	}
	return siz[u];
}
int dfn[N],top[N],tip=1;
void dfs2(int u,int father,int op){
	if (op==1) top[u]=top[father];
	dfn[u]=tip++;
	if (son[u]!=0) dfs2(son[u],u,1);
	for (auto v:e[u]){
		if (v==father||v==son[u]) continue;
		dfs2(v,u,0);
	}
}
struct dot{
	int ls,rs,val;
}d[N<<5];
struct tree{
	int cntdot=0;
	void build(int &cnt,int l,int r){
		cnt=++cntdot;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(d[cnt].ls,l,mid);
		build(d[cnt].rs,mid+1,r);
	}
	void insert(int &cnt,int pre,int l,int r,int id){
		cnt=++cntdot;
		d[cnt].ls=d[pre].ls,d[cnt].rs=d[pre].rs,d[cnt].val=d[pre].val+1;
		if (l==r) return;
		int mid=(l+r)>>1;
		if (id<=mid) insert(d[cnt].ls,d[pre].ls,l,mid,id);
		if (id>mid) insert(d[cnt].rs,d[pre].rs,mid+1,r,id);
	}
	int query(int u,int v,int _lca,int flca,int l,int r,int k){
		if (l==r) return l;
		int mid=(l+r)>>1,x=d[d[v].ls].val+d[d[u].ls].val-d[d[_lca].ls].val-d[d[flca].ls].val;
		if (x>=k) return query(d[u].ls,d[v].ls,d[_lca].ls,d[flca].ls,l,mid,k);
		if (x<k) return query(d[u].rs,d[v].rs,d[_lca].rs,d[flca].rs,mid+1,r,k-x);
	}
}book;
int lca(int x,int y){
	if (top[x]==top[y]) return dep[x]>dep[y]?y:x;
	if (dep[top[x]]<dep[top[y]]) swap(x,y);
	return lca(fa[top[x]],y);
}
signed main(){
	int n=read(),m=read();
	for (int i=1;i<=n;i++) a[i]=b[i]=read(),top[i]=i;
	for (int i=1;i<n;i++){
		int u=read(),v=read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0),dfs2(1,0,0);
	sort(b+1,b+n+1);
	sz=unique(b+1,b+n+1)-b-1;
	book.build(root[0],1,sz);
	for (int i=1;i<=n;i++){
		int id=lower_bound(b+1,b+sz+1,a[i])-b;
		book.insert(root[i],root[fa[i]],1,sz,id);
	}
	int lst=0;
	while (m--){
		int x=read()^lst,y=read(),z=read();
		int _lca=lca(x,y);cout<<x<<'\n';
		int ans=b[book.query(root[x],root[y],root[_lca],root[fa[_lca]],1,sz,z)];
		cout<<ans<<'\n';
		lst=ans;
	}
	return 0;
}