rt

题目传送门

我的代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;
struct edge{
	int to,nxt;
}e[N<<1];
int head[N],cnt;
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int dep[N],f[N],siz[N],son[N],st[N],ed[N],eul[N],idx;
void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;
	f[u]=fa;
	siz[u]=1;
	st[u]=++idx,eul[idx]=u;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
	ed[u]=++idx,eul[idx]=u;
}
int top[N];
void dfs2(int u,int fa){
	top[u]=fa;
	if(!son[u]) return;
	dfs2(son[u],fa);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	return u;
}
int p[N],col[N];
int bl[N],M;
struct node{
	int l,r,id,LCA;
	friend bool operator<(node x,node y){
		if(bl[x.l]==bl[y.l]){
			return x.r<y.r;
		}
		else return x.l<y.l;
	}
}op[N];
int n,m,l=1,r=0;
int t[N],ans;
int res[N];
bool vis[N];
void add(int x){
	if(++t[col[x]]==1) ans++;
}
void delet(int x){
	if(--t[col[x]]==0) ans--;
}
void update(int x){
	if(vis[x]) delet(x);
	else add(x);
	vis[x]^=1;
} 
int main(){
	cin>>n>>m;
	M=n*2/sqrt(m*2/3);
	for(int i=1;i<=n;i++){
		cin>>col[i];
		p[i]=col[i];
	}
	sort(p+1,p+n+1);
	int k=unique(p+1,p+n+1)-p-1;
	for(int i=1;i<=n;i++){
		col[i]=lower_bound(p+1,p+k+1,col[i])-p;
	}
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
//	cout<<"---\n";
//	for(int i=1;i<=n;i++){
//		cout<<st[i]<<" "<<ed[i]<<endl;
//	}
//	cout<<"---\n";
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		int F=lca(u,v);
		bl[i]=(i-1)/M+1;
		op[i].id=i;
		if(u==F||v==F){
			if(st[v]<st[u]) swap(u,v);
			op[i].l=st[u],op[i].r=st[v];
		}
		else{
			if(ed[v]<st[u]) swap(u,v);
			op[i].l=ed[u],op[i].r=st[v],op[i].LCA=F;
		}
	} 
	sort(op+1,op+m+1);
//	cout<<"---\n";
//	for(int i=1;i<=m;i++){
//		cout<<eul[i]<<endl;
//	}
//	cout<<"---\n";
	for(int i=1;i<=m;i++){
		while(l<op[i].l) update(eul[l++]);
		while(l>op[i].l) update(eul[--l]);
		while(r>op[i].r) update(eul[r--]);
		while(r<op[i].r) update(eul[++r]);
		if(op[i].LCA) update(op[i].LCA);
		res[op[i].id]=ans;
		if(op[i].LCA) update(op[i].LCA);
	}
	for(int i=1;i<=m;i++) cout<<res[i]<<endl;
	return 0;
}