三个点都是差 1,查了一下午都没找到什么有问题的边界情况,懂不了一点,火大。
#include<stdio.h>
#include<vector>
#include<algorithm>
std::vector<int>edge[100001],tree[200001];
int n,dfn[200001],low[100001],dfntot,stk[200001],top,nodetot,f[200001][20],dep[200001],s[200001];
void tarjan(int u){
dfn[u]=low[u]=++dfntot,stk[++top]=u;
for(const auto&v:edge[u])
if(!dfn[v]){
tarjan(v),low[u]=low[v]<low[u]?low[v]:low[u];
if(low[v]==dfn[u]){
tree[u].push_back(++nodetot),tree[nodetot].push_back(u);
for(;stk[top]!=u;--top)tree[stk[top]].push_back(nodetot),tree[nodetot].push_back(stk[top]);
}
}else low[u]=dfn[v]<low[u]?dfn[v]:low[u];
}
void dfs(int u,int fa){
dfn[u]=++dfntot,f[u][0]=fa,dep[u]=dep[fa]+1,s[u]=s[fa]+(u<=n);
for(const auto&v:tree[u])
if(v!=fa)
dfs(v,u);
}
int lca(int u,int v){
if(dep[u]<dep[v])u^=v,v^=u,u^=v;
for(;dep[u]!=dep[v];u=f[u][__builtin_ctz(dep[u]-dep[v])]);
if(u==v)return u;
for(int i=20;i--;)
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
return f[u][0];
}
std::vector<int>h;
void work(){
int m;
scanf("%d%d",&n,&m),nodetot=n;
for(int u,v;m--;)scanf("%d%d",&u,&v),edge[u].push_back(v),edge[v].push_back(u);
dfntot=top=0,tarjan(1);
dfntot=0,dfs(1,0);
for(int j=1;j<20;++j)
for(int i=1;i<=nodetot;++i)
f[i][j]=f[f[i][j-1]][j-1];
int Q,k;
for(scanf("%d",&Q);Q--;){
scanf("%d",&k),h.resize(k);
for(auto&p:h)scanf("%d",&p);
std::sort(h.begin(),h.end(),[](const auto&x,const auto&y){return dfn[x]<dfn[y];});
int sum=-k;top=0;
for(const auto&p:h){
if(!top){stk[++top]=p;continue;}
int q=lca(stk[top],p);
if(q!=stk[top]){
for(sum+=s[stk[top]];dfn[stk[top-1]]>=dfn[q];--top);
sum-=s[stk[top]=q];
}stk[++top]=p;
}
printf("%d\n",sum+=s[stk[top]]-s[f[stk[1]][0]]);
}
for(int i=1;i<=n;++i)edge[i].clear();
for(int i=1;i<=nodetot;++i)dfn[i]=0,tree[i].clear();
}
int main(){
int T;
scanf("%d",&T);
for(;T--;work());
return 0;
}