求spoj公共账号，或者帮忙交一下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3fll

const int N=1e5+10;

int pos[N],a[N],b[N],fa[N][32],dep[N],st[N],ed[N],c[N*3],cnt[N],vis[N],ans[N],tim,sum,n,m;
struct P{int id,l,r,x;}q[N];
vector<int> e[N];

bool cmp(P u,P v)
{
	if(pos[u.l]!=pos[v.l]) return pos[u.l]<pos[v.l];
	else if(pos[u.l]&1) return u.r<v.r;
	else return u.r>v.r;
}

inline void modify(int x)
{
	if(vis[x])
	{
		cnt[a[x]]--;
		if(cnt[a[x]]==0) sum--;
	}
	else
	{
		cnt[a[x]]++;
		if(cnt[a[x]]==1) sum++;
	}
	vis[x]^=1;
}

void dfs(int u)
{
	st[u]=++tim;
	c[tim]=u;
	for(int v:e[u])
	{
		if(v!=fa[u][0])
		{
			fa[v][0]=u;
			dep[v]=dep[u]+1;
			dfs(v);
		}
	}
	ed[u]=++tim;
	c[tim]=u;
}

int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	memcpy(b,a,sizeof(b));
	sort(b+1,b+n+1);
	int tot=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
	dep[1]=1;
	dfs(1);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin >> x >> y;
		if(dep[x]>dep[y]) swap(x,y);
		int t=lca(x,y);
		if(t==x) q[i]={i,st[x],st[y],0};
		else q[i]={i,ed[x],st[y],t};
	}
	int block=sqrt(n);
	for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=n;i++)
	{
		while(q[i].l<l) modify(c[--l]);
		while(r<q[i].r) modify(c[++r]);
		while(l<q[i].l) modify(c[l++]);
		while(q[i].r<r) modify(c[r--]);
		if(q[i].x) modify(q[i].x);
		ans[q[i].id]=sum;
		if(q[i].x) modify(q[i].x);
	}
	for(int i=1;i<=m;i++) cout << ans[i] << '\n';
	return 0;
}