Description
给定一张 \(n\) 个点 \(m\) 条边的无向联通图，共有 \(q\) 次操作，每次操作选择一些点作为关键点，询问有多少个点满足删去该点及与其相邻的边后，至少有两个关键点不能互相到达。\(n,q\leq 10^5,m\leq 2\cdot 10^5,\sum|S|\leq 2\cdot 10^5\)。
Sol
还是挺简单的。
就是圆方树+虚树\(\mathrm{DP}\)。
但是让我们看到了未来毒瘤的方向，出题人已经开始把树上问题放到图上了。
先把圆方树建出来，观察到两点之间的必经点就是圆方树上两点之间路径的圆点个数。
那就可以虚树\(\mathrm{DP}\)了，记录 \(dep[x]\) 表示从根到 \(x\) 有多少点是圆点，对于虚树上的每条边 \((x,y)\) 计算一下 \(dep[fa[y]]-dep[x]\) 就是这条边上圆点的贡献。然后再考虑在虚树上的点怎么计算，对于点 \(x\)，如果 \(x\) 超过两个子树有关键点，或者 \(x\) 子树外还有关键点，那么 \(x\) 一定是必经点，随便判一下就好了。
然后调了一个小时的原因是倍增的 \(lg\) 数组只预处理到了 \(n\)，但是建成圆方树之后深度有可能比 \(n\) 大。
Code
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=8e5+5;
int lg[N],d[N],f[N][20],ans,len;
int n,m,q,cnt,a[N],sze[N],dfn[N],low[N],head2[N];
int head[N],siz[N],dep[N],sum,stk[N],top,tot,is[N];
struct Edge{
int to,nxt;
}edge[N<<1],edge2[N<<1];
bool cmp(int x,int y){
return dfn[x]<dfn[y];
}
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
void add2(int x,int y){
edge2[++cnt].to=y;
edge2[cnt].nxt=head2[x];
head2[x]=cnt;
}
void tarjan(int now){
dfn[now]=low[now]=++tot;
stk[++top]=now;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to]){
tarjan(to); low[now]=min(low[now],low[to]);
if(low[to]>=dfn[now]){
sum++; int z;
do{
z=stk[top--];
add2(sum,z),add2(z,sum);
} while(z!=to);
add2(sum,now),add2(now,sum);
}
} else low[now]=min(low[now],dfn[to]);
}
}
void clear(){
cnt=tot=sum=top=0;
memset(d,0,sizeof d);
memset(f,0,sizeof f);
memset(is,0,sizeof is);
memset(dep,0,sizeof dep);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(stk,0,sizeof stk);
memset(sze,0,sizeof sze);
memset(head,0,sizeof head);
memset(head2,0,sizeof head2);
}
void dfs(int now,int fa=0){
sze[now]=(now<=n); dfn[now]=++tot;
for(int i=head2[now];i;i=edge2[i].nxt){
int to=edge2[i].to;
if(fa==to) continue;
dep[to]=dep[now]+(to<=n);
f[to][0]=now; d[to]=d[now]+1;
for(int j=1;j<=lg[d[to]];j++) f[to][j]=f[f[to][j-1]][j-1];
dfs(to,now); sze[now]+=sze[to];
}
}
int lca(int x,int y){
if(d[x]<d[y]) swap(x,y);
for(int j=lg[d[x]];~j;j--) if(d[f[x][j]]>=d[y]) x=f[x][j];
if(x==y) return x;
for(int j=lg[d[x]];~j;j--) if(f[x][j]!=f[y][j]) x=f[x][j],y=f[y][j];
return f[x][0];
}
void ins(int x){
if(top<=1) return stk[++top]=x,void();
int LCA=lca(stk[top],x);
if(stk[top]==LCA) return stk[++top]=x,void();
while(top>1 and dfn[stk[top-1]]>=dfn[LCA]) add(stk[top-1],stk[top]),top--;
if(LCA!=stk[top]) add(LCA,stk[top]),stk[top]=LCA;
stk[++top]=x;
}
void dfs2(int now){
siz[now]=(is[now]==q);
int flag=0;
for(int &i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
dfs2(to);
if(siz[to] and siz[to]!=len)
ans+=dep[f[to][0]]-dep[now],flag++;
siz[now]+=siz[to];
} if((siz[now]<len or flag>1) and now<=n and is[now]!=q) ans++;
}
void work(){
scanf("%d",&len); ans=cnt=0;
for(int i=1;i<=len;i++)
scanf("%d",&a[i]),is[a[i]]=q;
std::sort(a+1,a+1+len,cmp);
top=0; if(is[1]!=q) stk[++top]=1;
for(int i=1;i<=len;i++) ins(a[i]);
while(top>1) add(stk[top-1],stk[top]),top--;
dfs2(1); printf("%d\n",ans);
}
void solve(){
clear();
scanf("%d%d",&n,&m);sum=n;
for(int i=2;i<=n<<1;i++)
lg[i]=lg[i-1]+((1<<lg[i-1]+1)==i);
for(int x,y,i=1;i<=m;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
cnt=0; tarjan(1);
memset(head,0,sizeof head);
dep[1]=d[1]=1; tot=0; dfs(1);
for(scanf("%d",&q);q;work(),q--);
}
signed main(){
int T;for(scanf("%d",&T);T;T--,solve());
return 0;
}