RE on #$\text{1 2 3 4 5}$

因为强制在线，实际是 WA。

求调

马蜂比较奇怪

#include<bits/stdc++.h>
#define pp(a) cout<<a<<'\n'
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
using namespace std;
const int N = 2e5 + 10;
struct node{
	node *ls,*rs;
	int data;
}tree[N << 5],*root[N],*tot;
struct edge{
	int u,v;
}e[N << 1];
int cnt = 0,h[N];
void add(int u,int v){
	e[++cnt].u = h[u];
	e[cnt].v = v;
	h[u] = cnt;
}
void insert(node* x,node* &y,int l,int r,int k){
//	cout << l << " " << r << " " << k << '\n';
	y = ++tot;
	*y = *x;
	y->data++;
//	cout << y->data << " " << y->ls << " " << y->rs << '\n';
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(k <= mid) insert(x->ls,y->ls,l,mid,k);
	else insert(x->rs,y->rs,mid + 1,r,k);
	y->data = y->ls->data + y->rs->data;
}
int query(node* x,node* y,node* lca,node* flca,int l,int r,int k){
	int sum = x->ls->data + y->ls->data - lca->ls->data - flca->ls->data;
	int mid = (l + r) >> 1;
	if(l == r) return l;
	if(k <= sum) return query(x->ls,y->ls,lca->ls,flca->ls,l,mid,k);
	else return query(x->rs,y->rs,lca->rs,flca->rs,mid + 1,r,k - sum);
}
int n,m;int disc[N];
int val[N];int f[N][20],dep[N];
void dfs1(int u,int fa){
	f[u][0] = fa;
	dep[u] = dep[fa] + 1;
	for(int i = 0;i <= 20;i++)
		f[u][i + 1] = f[f[u][i]][i];
//		cout << dep[u] << " " << u << '\n';
	for(int i = h[u];i;i = e[i].u){
//		cout << u << "->" << e[i].v << '\n';
		int v = e[i].v;
		if(v == fa) continue;
		dfs1(v,u);
	}
}
int lca(int x,int y){
	if(dep[x] < dep[y]) swap(x,y);
	for(int i = 20;i >= 0;--i){
		if(dep[f[x][i]] >= dep[y]){
			x = f[x][i];
		}
		if(x == y) return x;
	}
	for(int i = 20;i >= 0;--i){
		if(f[x][i] != f[y][i]){
			x = f[x][i],y = f[y][i];
		}
	}
	return f[x][0];
}
int len;
void dfs2(int u,int fa){
//	cout << "query" << fa << " " << u << '\n';
	insert(root[fa],root[u],1,n,val[u]);
//	pp(u);
	for(int i = h[u];i;i = e[i].u){
		int v = e[i].v;
		if(v == fa) continue;
		dfs2(v,u);
	}
}
int main(){
//	freopen("P2633_1.in","r",stdin);
	memset(dep,1,sizeof dep);
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin >> n >> m;
	tree->ls=tree->rs=root[0]=tot = tree;
	for(int i = 1;i <= n;i++){
		cin >> disc[i];val[i] = disc[i];
	}
	for(int i = 1;i < n;i++){
		int u,v;cin >> u >> v;
		add(u,v),add(v,u);
	}
	sort(disc + 1,disc + n + 1);
	len = unique(disc + 1,disc + n + 1) - disc;
	for(int i = 1;i <= n;i++){
		val[i] = lower_bound(disc + 1,disc + len + 1,val[i]) - disc;
	}
//	for(int i = 1;i <= n;i++) cout << val[i] << " ";
//	cout << '\n';
	dfs1(1,0);
//	rep(i,1,10) pp(dep[i]);
	dfs2(1,0);
	int last = 0;
	for(int i = 1;i <= m;i++){
		int u,v,k;
		cin >> u >> v >> k;u ^= last;	
		int Lca = lca(u,v);
		last = disc[query(root[u],root[v],root[Lca],root[f[Lca][0]],1,n,k)];
		cout << last << '\n';
	}
}```