自动搬运

查看原文

来自洛谷，原作者为

	Mikefeng **

搬运于2025-08-24 22:47:29，当前版本为作者最后更新于2023-05-30 20:17:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：看到杨老师的 $O(n\log^2 n)$ 做法，所以来写一个 $O(n\sqrt n)$ 做法。

题意

多次查询包含区间中所有点的连通块最小大小。

做法

区间查询，可以离线，一眼鉴定为莫队。

包含所有关键点的连通块最小大小是经典问题，虚树中边的数量等于按 dfs 排序后两两相邻的点的距离之和。（第一个和最后一个也相邻）

这样就获得了 $O(n\sqrt n\log n)$ 的做法，直接莫队，记录每个点的出现数量，如果删到了 $0$ 就从点集中去掉，用 set 动态维护前驱后继，同时维护虚树大小。

因为懒得写回滚莫队，先写了 set，有 $28$ 分的高分。

发现只删的前驱后继可以用链表维护，套一个只删不加的回滚莫队，右端点从右到左排序，同时用 $O(1)$ lca 求两个点间的距离，用的是 dfs 序 lca，这样常数小，还不用多记一个欧拉序。

时间复杂度 $O(n\sqrt n)$。

代码

const int N=1e5+5;
int n,m,k,len,res;
int a[N],ans[N];
int num[N],lg[N];
vector<int> e[N];
int id[N],rk[N],dep[N];
int st[20][N],cnt;
inline void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	id[u]=++cnt;rk[cnt]=u;
	st[0][cnt]=fa;
	for(int v:e[u]) if(v!=fa) dfs(v,u);
}
inline int Min(int x,int y){return dep[x]<dep[y]?x:y;}
inline void init(){
	F(i,2,n) lg[i]=lg[i>>1]+1;
	F(j,1,19) F(i,1,cnt-(1<<j)+1) st[j][i]=Min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
inline int lca(int l,int r){
	if(l==r) return rk[l];
	if(l>r) swap(l,r);
	++l;int k=lg[r-l+1];
	return Min(st[k][l],st[k][r-(1<<k)+1]);
}
inline int dis(int x,int y){return dep[rk[x]]+dep[rk[y]]-2*dep[lca(x,y)];}
struct md{
	int l,r,bid,id;
	inline bool operator < (const md &x)const{return bid!=x.bid?l<x.l:r>x.r;}
}q[N];
int pre[N],nxt[N];
struct node{
	int pre,nxt,id;
	node(){}
	node(int pre,int nxt,int id):pre(pre),nxt(nxt),id(id){}
};
vector<node> s;
inline void Del(int x){
	--num[x];
	if(!num[x]){
		res-=dis(pre[x],x)+dis(x,nxt[x]);
		res+=dis(pre[x],nxt[x]);
		pre[nxt[x]]=pre[x];nxt[pre[x]]=nxt[x];
	}
}
inline void del(int x){
	s.emplace_back(pre[x],nxt[x],x);
	--num[x];
	if(!num[x]){
		res-=dis(pre[x],x)+dis(x,nxt[x]);
		res+=dis(pre[x],nxt[x]);
		pre[nxt[x]]=pre[x];nxt[pre[x]]=nxt[x];
	}
}
inline void solve(){
	int l=1,r=0;
	F(i,1,m){
		if(q[i].bid!=q[i-1].bid){
			memset(num,0,sizeof num);
			F(j,(q[i].bid-1)*len+1,k) ++num[id[a[j]]];
			int lst=0;F(j,1,n){
				pre[j]=lst;
				if(num[j]) lst=j;
			}
			F(j,1,n) if(!pre[j]) pre[j]=lst;
			lst=0;UF(j,n,1){
				nxt[j]=lst;
				if(num[j]) lst=j;
			}
			UF(j,n,1) if(!nxt[j]) nxt[j]=lst;
			res=0;
			F(j,1,n) if(num[j]) res+=dis(pre[j],j);
			r=k;
		}
		l=(q[i].bid-1)*len+1;
		while(r>q[i].r) Del(id[a[r--]]);
		int now=res;
		while(l<q[i].l) del(id[a[l++]]);
		ans[q[i].id]=res/2+1;
		res=now;
		while(!s.empty()){
			node tmp=s.back();s.pop_back();
			if(!num[tmp.id]) nxt[tmp.pre]=tmp.id,pre[tmp.nxt]=tmp.id;
			++num[tmp.id];
		}
	}
}
bool M2;
int main(){
	int Time=clock();
	look_memory;
	n=read();k=read();m=read();
	len=sqrt(k);
	F(i,1,n-1){
		int u=read(),v=read();
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	dfs(1,0);init();
	F(i,1,k) a[i]=read();
	F(i,1,m) q[i].l=read(),q[i].r=read(),q[i].bid=(q[i].l-1)/len+1,q[i].id=i;
	sort(q+1,q+m+1);
	solve();
	F(i,1,m) cout<<ans[i]<<'\n';
	look_time;
	return 0;
}