题目
题解
很明显题目要求的就是两个点之间的割点数量，先建出圆方树，然后就是两两路径上圆点个数
可以建出虚树来求，也可以直接按$dfs$序排序，每个点和下一个点（$\vert S\vert$点的下一个点是$1$号点）求出路径圆点个数，然后除以$2$就是答案了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
using namespace std;
const int MAX=2e5+5;
struct p{
int x,y;
}c[MAX<<1];
int T,n,m,Q,cnt,tot,Top,num;
int st[MAX],s[MAX],h[MAX],dfn[MAX],low[MAX],fa[MAX],id[MAX],top[MAX],d[MAX],D[MAX],siz[MAX],son[MAX];
bool use[MAX];
vector<int> vec[MAX];
bool cmp(int a,int b) {return id[a]<id[b];}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num,c[++num]=(p){h[y],x},h[y]=num;}
void Add(int x,int y) {vec[x].push_back(y),vec[y].push_back(x);}
void Tarjan(int x,int fa=0)
{
st[++Top]=x,use[x]=1,dfn[x]=low[x]=++cnt;
for(int i=h[x],y;i;i=c[i].x)
if(fa^(y=c[i].y)) if(!dfn[y])
{
Tarjan(y,x);
if(low[y]>=dfn[x])
{
int tt=-1;
Add(x,++tot);
while(tt!=y) tt=st[Top--],use[tt]=0,Add(tot,tt);
}
low[x]=min(low[x],low[y]);
}
else if(use[x]) low[x]=min(low[x],dfn[y]);
}
void dfs(int x=1,int F=0)
{
fa[x]=F,d[x]=d[F]+(siz[x]=1),D[x]=D[F]+(x<=n),son[x]=0;
for(int y:vec[x])
if(F^y)
{
dfs(y,x),siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,id[x]=++cnt;
if(!son[x]) return;
dfs1(son[x],tp);
for(int y:vec[x])
if((y^fa[x])&&(y^son[x])) dfs1(y,y);
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
return d[x]>d[y]?y:x;
}
int Dis(int x,int y) {return D[x]+D[y]-(D[LCA(x,y)]<<1);}
int main()
{
T=read();
while(T--)
{
tot=n=read(),m=read(),num=cnt=0;
memset(h,0,sizeof(h));
memset(dfn,0,sizeof(dfn));
memset(vec,0,sizeof(vec));
for(int i=1;i<=m;++i)
add(read(),read());
for(int i=1;i<=n;++i)
if(!dfn[i]) Tarjan(i);
Q=read(),cnt=0,dfs(),dfs1();
for(int i=1,S,Ans;i<=Q;++i)
{
S=read(),Ans=0;
for(int j=1;j<=S;++j)
s[j]=read();
sort(s+1,s+1+S,cmp);
for(int j=1;j<S;++j)
Ans+=Dis(s[j],s[j+1]);
printf("%d\n",(Ans+Dis(s[S],s[1])>>1)-S+(LCA(s[S],s[1])<=n));
}
}
return 0;
}
