P4606 [SDOI2018] 战略游戏 对自己的警告--zhengjun

tarjan 多测的时候 dfn 数组要清空！！！

树剖多测的时候 son 数组要清空！！！

点双 tarjan 时可用 vector 建边，边双时用 vector 需要无重边

本题直接建圆方树，然后答案就是关键点构成的虚树上非关键原点个数。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10,V=N*2;
int T,n,m,k,q;
struct edges{
	int to,nex;
}edge[N*2];
int kk=1,head[N];
void addedge(int u,int v){
	edge[++kk]={v,head[u]},head[u]=kk;
	edge[++kk]={u,head[v]},head[v]=kk;
}
vector<int>to[V];
int cnt,dft,dfn[N],low[N],stk[N];
void add(int u,int v){
	to[u].push_back(v),to[v].push_back(u);
}
void tarjan(int u,int las=0){
	low[u]=dfn[u]=++dft,stk[++cnt]=u;
	for(int i=head[u],v;v=edge[i].to,i;i=edge[i].nex)if(i^las^1){
		if(!dfn[v]){
			tarjan(v,i),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				add(++k,u);
				do add(k,stk[cnt]);while(stk[cnt--]^v);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
int tot,fa[V],son[V],siz[V],dep[V],top[V],sum[V],bg[V];
void dfs1(int u){
	sum[u]=sum[fa[u]]+(u<=n);
	siz[u]=1,dep[u]=dep[fa[u]]+1;
	son[u]=0;
	for(int v:to[u])if(v^fa[u]){
		fa[v]=u,dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t,bg[u]=++tot;
	if(son[u])dfs2(son[u],t);
	for(int v:to[u])if(v^fa[u]&&v^son[u])dfs2(v,v);
}
int LCA(int u,int v){
	for(;top[u]^top[v];u=fa[top[u]]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
	}
	return dep[u]<dep[v]?u:v;
}
int t,a[N];
void get(){
	scanf("%d%d",&n,&m);
	for(int u,v;m--;){
		scanf("%d%d",&u,&v);
		addedge(u,v); 
	}
	k=n,cnt=dft=0,tarjan(1);
	tot=0,dfs1(1),dfs2(1,1);
	scanf("%d",&q);
	for(;q--;){
		scanf("%d",&t);
		for(int i=1;i<=t;i++)scanf("%d",&a[i]);
		sort(a+1,a+1+t,[](int x,int y){return bg[x]<bg[y];});
		stk[cnt=1]=a[1];
		int ans=0;
		auto add=[&](int t,int u){
			ans+=sum[u]-sum[t];
		};
		for(int i=2;i<=t;i++){
			int x=LCA(a[i],stk[cnt]);
			for(;cnt>1&&dep[stk[cnt-1]]>=dep[x];cnt--)add(stk[cnt-1],stk[cnt]);
			if(stk[cnt]^x)add(x,stk[cnt--]);
			if(stk[cnt]^x)stk[++cnt]=x;
			if(stk[cnt]^a[i])stk[++cnt]=a[i];
		}
		for(int i=1;i<cnt;i++)add(stk[i],stk[i+1]);
		ans+=stk[1]<=n;
		printf("%d\n",ans-t);
	}
}
void clear(){
	kk=1;
	for(int i=1;i<=n;i++)head[i]=dfn[i]=0;
	for(int i=1;i<=k;i++)to[i].clear();
}
int main(){
	freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	for(scanf("%d",&T);T--;clear())get();
	return 0;
}