照着题解区第一篇写的。但是空间是他的 10 倍啊。

开的数组空间算了一下感觉不是很大，但是跑出来有接近 200MB，有没有大佬帮忙看一看。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 40005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
const int S=1000;
bitset<maxn>f[maxn/S+5][maxn/S+5],s;
int id[maxn],times,n,m,a[maxn],g[maxn];
int stac[maxn],tot,deep[maxn],mxdeep[maxn],fa[maxn],top[maxn],siz[maxn],son[maxn],bfa[maxn];
vector<int>to[maxn];//存边
void dfs1(int x,int pre) {
	fa[x]=pre;siz[x]=1;deep[x]=mxdeep[x]=deep[pre]+1;
	for (auto y:to[x]) if (y^pre) {
		dfs1(y,x);siz[x]+=siz[y];
		mxdeep[x]=max(mxdeep[x],mxdeep[y]);
		if (!son[x]||siz[son[x]]<siz[y]) son[x]=y;
	}
	if (mxdeep[x]-deep[x]>=S) id[x]=++times,mxdeep[x]=deep[x]+1;
}
void dfs2(int x,int pre) {
	int i;
	if (id[x]) stac[++tot]=x;
	if (id[x]) f[id[x]][id[x]][a[x]]=1;
	if (id[x]&&tot>1) {
		int tmp=id[stac[tot-1]],now=x;
		bfa[x]=stac[tot-1];
		f[id[x]][tmp][a[x]]=1;
		while (now!=stac[tot-1]) now=fa[now],f[id[x]][tmp][a[now]]=1;
		for (i=tot-2;i>=1;i--) {
			f[id[x]][id[stac[i]]]=f[id[x]][id[stac[i+1]]]|f[id[stac[i+1]]][id[stac[i]]];		
		}
		// gdb(x,stac[tot-1],f[id[x]][id[stac[tot-1]]].count());
	}
	for (auto y:to[x]) if (y^pre) dfs2(y,x);
	if (id[x]) tot--;
}
void dfs3(int x,int pre,int u) {
	top[x]=u;
	if (!son[x]) return ;
	dfs3(son[x],x,u);
	for (auto y:to[x]) if (y!=pre&&y!=son[x]) dfs3(y,x,y);
}
int query(int x,int y) {
	while (top[x]^top[y]) {
		if (deep[top[x]]<deep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return deep[x]<deep[y]?x:y; 
}
signed main(void){
	freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	int i,x,y,las=0;
	read(n);read(m);
	for (i=1;i<=n;i++) read(a[i]),g[i]=a[i];
	sort(g+1,g+1+n);
	int cnt=unique(g+1,g+1+n)-g-1;
	for (i=1;i<=n;i++) a[i]=lower_bound(g+1,g+1+cnt,a[i])-g;
	
	for (i=1;i<n;i++) {
		read(x),read(y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	dfs1(1,0);
	if (!id[1]) id[1]=++times;
	dfs2(1,0);
	dfs3(1,0,1);
	while (m--) {
		read(x);read(y);x^=las;
		// gdb(x,y);
		assert(x<=n&&y<=n);
		int g=query(x,y);s.reset();
		while (x!=g&&!id[x]) s.set(a[x]),x=fa[x];
		while (y!=g&&!id[y]) s.set(a[y]),y=fa[y];
		s[a[g]]=1;
		if (x!=g) {
			int now=x;
			while (deep[bfa[now]]>=deep[g]) now=bfa[now];
			s|=f[id[x]][id[now]];
			while (now!=g) s.set(a[now]),now=fa[now];   
		}
		if (y!=g) {
			int now=y;
			while (deep[bfa[now]]>=deep[g]) now=bfa[now];
			s|=f[id[y]][id[now]];
			while (now!=g) s.set(a[now]),now=fa[now];
		}
		las=s.count();
		
		printf("%d\n",las);
	}
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i