树上莫队

样例输入，程序输出 4 5

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define Rep(i,a,b) for(register int i=a;i>=b;--i)
inline int read()
{
	int x=0;bool f=0;char ch;
	do{ch=getchar();f|=(ch=='-');}while(!isdigit(ch));
	do{x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}while(isdigit(ch));
	return f?-x:x;
}
inline void write(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writesp(int x)
{
	write(x);putchar(' ');
}
inline void writeln(int x)
{
	write(x);puts("");
}
int head[maxn],to[maxn<<1|1],nxt[maxn<<1|1],tot=0;
void add(int u,int v)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}
int ord[maxn<<1|1],ccnt=0,first[maxn],last[maxn];
int a[maxn],b[maxn];
int blo;
struct query
{
	int l,r,lca,id;
	bool operator <(const query &b)const
	{
		return (id/blo!=b.id/blo)?(id/blo<b.id/blo):((id/blo+1)&1?r<b.r:r>b.r);
	}
}q[maxn];
int anc[maxn][31],dep[maxn];
void dfs(int u)
{
	ord[++ccnt]=u;
	first[u]=ccnt;
	for(register int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==anc[u][0])continue;
		dep[v]=dep[u]+1;anc[v][0]=u;
		rep(i,1,30)anc[v][i]=anc[anc[v][i-1]][i-1];
		dfs(v);
		
	}
	ord[++ccnt]=u;
	last[u]=ccnt;
}
int lca(int u ,int v)
{
	if(dep[v]>dep[u])swap(u,v);
	Rep(i,30,0)if(dep[anc[u][i]]>=dep[v])u=anc[u][i];
	if(u==v)return u;
	Rep(i,30,0)
	{
		if(anc[u][i]!=anc[v][i])u=anc[u][i],v=anc[v][i];
	}
	return anc[u][0];
}
int cnt[maxn],vis[maxn],l=1,r=0;int ans=0;
void work(int x)
{
	vis[x]?ans-=!--cnt[x]:ans+=!cnt[x]++;vis[x]^=1;
}
//void del(int x)
//{
//	--cnt[x];if(!cnt[x])--ans;
//}
//void add(int x)
//{
//	if(!cnt[x])++ans;++cnt[x];
//}
int res[maxn];
int main()
{
	int n=read(),m=read();
	rep(i,1,n)
	{
		a[i]=b[i]=read();
	}
	sort(b+1,b+1+n);
	int asdf=unique(b+1,b+1+n)-b-1;
	rep(i,1,n)
	{
		a[i]=lower_bound(b+1,b+1+asdf,a[i])-b;
	}
	rep(i,1,n-1)
	{
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	dep[1]=1;
	dfs(1);
	blo=sqrt(m);
	rep(i,1,m)
	{
		int x=read(),y=read();int ttt=lca(x,y);
		if(first[x]>first[y])swap(x,y);
		if(ttt==x)
		{
			q[i].l=first[x];q[i].r=first[y];
		}
		else
		{
			q[i].l=last[x];q[i].r=first[y];q[i].lca=ttt;
		}
		q[i].id=i;
	}
	sort(q+1,q+1+m);
	rep(i,1,m)
	{
		int ql=q[i].l,qr=q[i].r;
		while(l<ql)work(ord[l++]);
		while(l>ql)work(ord[--l]);
		while(r<qr)work(ord[++r]);
		while(r>qr)work(ord[r--]);
		if(q[i].lca)work(q[i].lca);
		res[q[i].id]=ans;
		if(q[i].lca)work(q[i].lca);
	}
	rep(i,1,m)writeln(res[i]);
	return 0;
}