RT，以下代码弱化版可以通过，spoj 上评测到 running master judge 后就报 WA 了。翻了一遍讨论区无果。

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn=1e5+10;

int n,m,q,B;
int a[maxn],b[maxn];
vector<int> ve[maxn];

int dep[maxn],fa[maxn],son[maxn],sz[maxn];
void dfs1(int u)
{
	dep[u]=dep[fa[u]]+1,sz[u]=1;
	for(int i=0;i<ve[u].size();++i)
		if(ve[u][i]^fa[u])
			fa[ve[u][i]]=u,dfs1(ve[u][i]),
			sz[u]+=sz[ve[u][i]],son[u]=(sz[ve[u][i]]>sz[son[u]])?ve[u][i]:son[u];
}

int timer;
int tp[maxn];
int seq[maxn];
int st[maxn],ed[maxn];
void dfs2(int u,int topf)
{
	st[u]=++timer,seq[timer]=u,tp[u]=topf;
	if(son[u]) dfs2(son[u],topf);
	for(int i=0;i<ve[u].size();++i) if(ve[u][i]^fa[u]&&ve[u][i]^son[u]) dfs2(ve[u][i],ve[u][i]);
	ed[u]=++timer,seq[timer]=u;
}
int lca(int x,int y){
	while(tp[x]^tp[y]){
		if(dep[tp[x]]<dep[tp[y]]) x^=y^=x^=y;
		x=fa[tp[x]];
	}
	return dep[x]>dep[y]?y:x;
}

int ans;
int res[maxn];
int cnt[maxn],est[maxn];
struct query{
	int Lca;
	int l,r,id,bl;
}qry[100005]; 

int getB(int x){ return (x+B-1)/B; }
bool cmp(query xx,query yy){ return xx.bl==yy.bl?xx.r<yy.r:xx.bl<yy.bl; }
void upd(int x){
	if(est[x]) ans-=(!(--cnt[a[x]]));
	else ans+=((++cnt[a[x]])==1);
	est[x]^=1;
}
signed main()
{
	scanf("%d%d",&n,&q);
	B=max((int)sqrt(q),1);
	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,u,v;i<n;++i) scanf("%d%d",&u,&v),ve[u].pb(v),ve[v].pb(u);
	dfs1(1),dfs2(1,1);
	for(int i=1;i<=q;++i)
	{
		int x,y;scanf("%d%d",&x,&y);
		int l=lca(x,y);
		if(st[x]>st[y]) x^=y^=x^=y;
		qry[i].id=i;
		if(l==x) qry[i].l=st[x],qry[i].r=st[y];
		else qry[i].l=ed[x],qry[i].r=st[y],qry[i].Lca=l;
		qry[i].bl=getB(qry[i].l);
	}
	sort(qry+1,qry+1+q,cmp);
	int l=1,r=0;
	for(int i=1;i<=q;++i)
	{
		while(l>qry[i].l) upd(seq[--l]);
		while(r<qry[i].r) upd(seq[++r]);
		while(l<qry[i].l) upd(seq[l++]);
		while(r>qry[i].r) upd(seq[r--]);
		if(qry[i].Lca) upd(qry[i].Lca);
		res[qry[i].id]=ans;
		if(qry[i].Lca) upd(qry[i].Lca);
	}
	for(int i=1;i<=q;++i) printf("%d\n",res[i]);
	return 0;
}