rt。

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>p[400005];
int st[400005],ed[400005];
int a[400005];
int son[200005],top[200005],sz[200005],dep[200005],f[200005],nw =0,q[200005];//q是点权，st,ed代表一个点在欧拉序上的两个位置
//树链剖分预处理部分，夹杂一个树上欧拉序
void dfs1(int now,int fa){
	int mx =0;sz[now] = 1;f[now] = fa;
	st[now] = ++nw,a[nw] = q[now];dep[now] =dep[fa]+1;
	for(int i = 0;i<p[now].size();i++){
		if(p[now][i]!=fa){
			dfs1(p[now][i],now);
			sz[now]+=sz[p[now][i]];
			if(sz[p[now][i]]>mx){
				mx = sz[p[now][i]],son[now] = p[now][i];
			}
		}
	}ed[now] = ++nw,a[nw] = q[now];
//	cout << nw << '\n';
}void dfs2(int now,int ok){
	if(ok == 1)top[now] = now;
	else top[now] = top[f[now]];
	for(int i =0;i<p[now].size();i++){
		if(p[now][i]==son[now])dfs2(p[now][i],0);
	}for(int i =0;i<p[now].size();i++){
		if(p[now][i]!=son[now] and p[now][i]!=f[now])dfs2(p[now][i],1);
	}return;
}int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x = f[top[x]];
	}if(dep[x]>dep[y])swap(x,y);
	return x;
}//经过lca板子题验证，lca部分并没有问题
//莫队预处理
int d[400005],l[1005],r[1005];
void init(){
	int sq = sqrt(2*n);
	for(int i = 1;i<=sq;i++)l[i] = (i-1)*sq+1,r[i] = i*sq;
	r[sq] = 2*n;
	for(int i =1;i<=sq;i++)for(int j = l[i];j<=r[i];j++)d[j] = i;
	return;
}struct node{
	int l,r,id,x,y;
}; vector<node>query;
bool cmp(node a,node b){
	if(d[a.l] == d[b.l]){
		if(d[a.l]%2)return d[a.r]>d[b.r];
		else return d[a.r]<d[b.r];
	}return d[a.l]<d[b.l];
}int ans[100005],used[100005],tong[100005],nww= 0;
void add(int x){
	if(++tong[x] == 1)nww++;
}void del(int x){
	if(--tong[x] == 0)nww--;
}void Add(int x){
	if(used[x])del(x);
	else add(x);used[x]^=1;
}
void Mo(){
	int ll =1,rr = 0;
	for(int i =0;i<query.size();i++){
		int al = query[i].l,ar = query[i].r,x = query[i].x,y= query[i].y,ok =0;
		while(ll>al)Add(a[--ll]);
		while(rr<ar)Add(a[rr++]);
		while(ll<al)Add(a[ll++]);
		while(rr>ar)Add(a[rr--]);
		int lc = lca(x,y);
		if(lc!=x and lc!=y){
			ok = 1;Add(q[lc]);
		}ans[query[i].id] = nww;
		if(ok)Add(q[lc]);
	}for(int i = 1;i<=m;i++)cout << ans[i] << '\n';
}
signed main(){
	cin >> n >> m;
	vector<int>ll;
	for(int i = 1;i<=n;i++)cin >> q[i];
	for(int i = 1;i<n;i++){
		int a,b;cin >> a >> b;p[a].push_back(b),p[b].push_back(a);
	}
	for(int i =1;i<=n;i++)ll.push_back(q[i]);
	sort(ll.begin(),ll.end());ll.erase(unique(ll.begin(),ll.end()),ll.end());//离散化
	for(int i = 1;i<=n;i++)q[i] = lower_bound(ll.begin(),ll.end(),q[i])-ll.begin()+1;
	dfs1(1,0);dfs2(1,1);init();
	for(int i = 1;i<=m;i++){
		int x,y;cin >> x >> y;
		if(st[x]>st[y])swap(x,y);
		node nd;nd.x = x,nd.y = y;nd.id = i;
		if(lca(x,y) == x or lca(x,y)== y){
			nd.l = st[x],nd.r = st[y];
		}else nd.l = ed[x],nd.r = st[y];
		query.push_back(nd);
	}sort(query.begin(),query.end(),cmp);
  //离线查询
	//for(int i = 1;i<=2*n;i++)cout << a[i] << ' ';
	Mo();
}