[SDOI2018]战略游戏（圆方树+虚树）

喜闻乐见的圆方树+虚树

图上不好做，先建出圆方树。

然后答案就是没被选到的且至少有两条边可以走到被选中的点的圆点的数量。

语文不好，但结论画画图即可得出。

然后套路建出虚树。

发现在虚树上DP可以得出答案。

所以在虚树上DP即可。

代码极丑

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=401000;

struct Graph{

	struct edge{

		int to,nxt;

	}e[N*2];

	int cnt,head[N];

	void add_edge(int u,int v){

		cnt++;

		e[cnt].nxt=head[u];

		e[cnt].to=v;

		head[u]=cnt;

	}

}g1,g2,g3;

int dfn[N],low[N],tim,stack[N],top,num;

void Tarjan(int u){

	dfn[u]=low[u]=++tim;

	stack[++top]=u;

	for(int i=g1.head[u];i;i=g1.e[i].nxt){

		int v=g1.e[i].to;

		if(dfn[v]==0){

			Tarjan(v);

			low[u]=min(low[u],low[v]);

			if(low[v]>=dfn[u]){

				g2.add_edge(++num,u);

				g2.add_edge(u,num);

				int x;

				do{

					x=stack[top--];

					g2.add_edge(x,num);

					g2.add_edge(num,x);

				}while(x!=v);

			}

		}

		else low[u]=min(low[u],dfn[v]);

	}

}

int w[N],fa[N][22],dep[N],tot,n;

void dfs(int u,int f){

	w[u]=w[f]+(u<=n?1:0);

	fa[u][0]=f;dep[u]=dep[f]+1;dfn[u]=++tot;

	for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];

	for(int i=g2.head[u];i;i=g2.e[i].nxt){

		int v=g2.e[i].to;

		if(v==f)continue;

		dfs(v,u);

	}

}

bool cmp(int x,int y){

	return dfn[x]<dfn[y];

}

int getlca(int x,int y){

	if(dep[x]<dep[y])swap(x,y);

	for(int i=20;i>=0;i--)

		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];

	if(x==y)return x;

	for(int i=20;i>=0;i--)

		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

	return fa[x][0];

}

int q[N],Tot;

void ins(int x){

	if(top<=1){stack[++top]=x;return;}

	int lca=getlca(stack[top],x);

	if(lca==stack[top]){stack[++top]=x;return;}

	while(top&&dfn[stack[top-1]]>=dfn[lca])g3.add_edge(stack[top-1],stack[top]),top--;

	if(stack[top]!=lca)g3.add_edge(lca,stack[top]),stack[top]=lca,q[++Tot]=lca;

	stack[++top]=x;

}

int ans;

bool book[N];

void get_ans(int u){

	if(u==1&&book[u]==0){

		int tmp=0;

		for(int i=g3.head[u];i;i=g3.e[i].nxt)tmp++;

		if(tmp==1){

			for(int i=g3.head[u];i;i=g3.e[i].nxt){

				int v=g3.e[i].to;

				get_ans(v);

			}

			return;

		}

	}

	if(!book[u]&&u<=n)ans++;

	for(int i=g3.head[u];i;i=g3.e[i].nxt){

		int v=g3.e[i].to;

		ans+=w[v]-w[u];

		if(v<=n)ans--;

		get_ans(v);

	}

}

void clear(){

	while(Tot)book[q[Tot]]=g3.head[q[Tot]]=0,Tot--;

	g3.cnt=0;top=0;ans=0;

}

void init(){

	memset(g1.head,0,sizeof(g1.head));

	g1.cnt=0;

	memset(g2.head,0,sizeof(g2.head));

	g2.cnt=0;

	tim=0;top=0;tot=0;

	memset(dfn,0,sizeof(dfn));

}

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

int m,Q,a[N];

int main(){

//	freopen("xdx.out","w",stdout);

	int T=read();

	while(T--){

		init();

		num=n=read();m=read();

		for(int i=1;i<=m;i++){

			int u=read(),v=read();

			g1.add_edge(u,v);g1.add_edge(v,u);

		}

		Tarjan(1);

		dfs(1,0);

		Q=read();

		while(Q--){

			clear();

			int k=read();

			for(int i=1;i<=k;i++)a[i]=read(),book[a[i]]=1,q[++Tot]=a[i];

			sort(a+1,a+1+k,cmp);

			if(a[1]!=1)stack[++top]=1,q[++Tot]=1;

			for(int i=1;i<=k;i++)ins(a[i]);

			for(int i=1;i<top;i++)g3.add_edge(stack[i],stack[i+1]);

			get_ans(1);

			printf("%d\n",ans);

		}

	}

	return 0;

}