不在同一个簇的两点的lca应该是界点吧

#include<bits/stdc++.h>
using namespace std;
int n,m,b,u,v,idx,top,lst,tot,dep[40001],bel[40001],a[40001],fa[40001],up[40001],down[40001],near[40001],stk[40001],rest[40001],has[40001],wait[40001];
vector <int> s,G[40001];
unordered_map <int,int> id;
bitset <40001> col[401];
void add(int u,int v){
	if(!v) v=s.back();
	bel[v]=++tot;
	for(int i=v;i!=fa[u];i=fa[i]) near[i]=i,col[tot][a[i]]=1;
	for(auto i:s){
		up[i]=u,down[i]=v;
		for(int j=i;!near[j];j=fa[j],near[i]=j);
	}
	s.clear();
}
void build(int u,int x){
	fa[u]=x,rest[u]=top,wait[u]=1,dep[u]=dep[x]+1;
	for(auto i=G[u].begin();i!=G[u].end();i++){
		if(*i==x){
			G[u].erase(i);
			break;
		}
	}
	int siz=0,cur=0,cnt=0,k=rest[u]+1;
	for(auto v:G[u]){
		stk[++top]=v;
		build(v,u);
		wait[u]+=wait[v];
		if(has[v]) siz++,has[u]=has[v];
	}
	if(!x||wait[u]>b||siz>1){
		wait[u]=0,has[u]=u;
		for(int i=0;i<=G[u].size();i++){
			int v=(i!=G[u].size()?G[u][i]:0);
			if(cnt+wait[v]>b||has[v]&&cur||!v){
				for(;(k<rest[v]||!v)&&k<=top;k++) s.push_back(stk[k]);
				add(u,cur),cur=cnt=0;
			}
			cnt+=wait[v],has[v]&&(cur=has[v]);
		}
		top=rest[u];
	}
}
int query(int u,int v){
	bitset <40001> ans;
	ans.reset();
	if(down[u]==down[v]){
		while(u!=v){
			if(dep[u]>dep[v]) ans[a[u]]=1,u=fa[u];
			else ans[a[v]]=1,v=a[v];
		}
	}
	else{
		int lu=down[u],lv=down[v];
		while(down[u]==lu) ans[a[u]]=1,u=fa[u];
		while(down[v]==lv) ans[a[v]]=1,v=fa[v];
		while(u!=v){
			if(dep[up[u]]>dep[up[v]]) ans|=col[bel[u]],u=up[u];
			else ans|=col[bel[v]],v=up[v];
		}
	}
	return ans.count();
}
int main(){
	scanf("%d%d",&n,&m),b=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=(id[a[i]]?id[a[i]]:id[a[i]]=++idx);
	for(int i=2;i<=n;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	build(1,0);
	while(m--){
		scanf("%d%d",&u,&v),u^=lst;
		printf("%d\n",lst=query(u,v));
	}
	return 0;
}