题目大意：
给一个$G=(V,E)$，满足$|V|=n$,$|E|=m$，且保证图联通，有Q个询问，每组询问有s个点，求图中有多少点满足：将其删去后，这s个点中存在一对点集$(a,b)$不联通且删去点不为s中的点。
$n,m,\sum s$均为$1e5$级别。
题解：
显然满足性质的点都是割点。
我们建一颗圆方树，然后考虑对于每组询问为所有点之间路径覆盖的割点数量。
用虚树+树剖维护即可。
不是很难，但考场上把点双写错，多调了1h。
代码：
#include "bits/stdc++.h"
using namespace std;
inline int read() {
int s=0,k=1;char ch=getchar();
while (ch<'0'|ch>'9') ch=='-'?k=-1:0,ch=getchar();
while (ch>47&ch<='9') s=s*10+(ch^48),ch=getchar();
return s*k;
}
const int N=2e5+10;
struct edges {
int v;edges *last;
};
int n,m;
int low[N],dfn[N],stk[N],bcc_cnt,top,idx,rt,son,cut[N],bel[N],pos[N];
vector<int> bcc[N];
int ga[N],fat[N],rid[N],size[N],heavy[N],tid[N],dfx,ncut[N],deep[N];
struct Group{
inline void Clear(){ecnt=edge;memset(head,0,sizeof head);}
edges edge[N<<2],*head[N],*ecnt;
inline void push(int u,int v){
*ecnt=(edges){v,head[u]},head[u]=ecnt++;
*ecnt=(edges){u,head[v]},head[v]=ecnt++;
}
inline void tarjan(int x,int fa) {
low[x]=dfn[x]=++idx;
for (edges *i=head[x];i;i=i->last) if ((fa^1)!=i-edge){
if (!dfn[i->v]) {
if (x==rt) ++son;
stk[++top] = i-edge;
tarjan(i->v,i-edge);
if (low[i->v]>=dfn[x]) {
int t=0;bcc_cnt++;
bcc[bcc_cnt].clear();
do {
t=stk[top--];
bcc[bcc_cnt].push_back(edge[t].v);
}while (t!=i-edge);
bcc[bcc_cnt].push_back(x);
cut[x]=true;
} else low[x]=min(low[i->v],low[x]);
} else if (dfn[i->v]<low[x]){
low[x] = dfn[i->v];
}
}
}
inline void tarjan(){
rt=1;son=0;
tarjan(1,-1);
if (son>1) cut[1]=true;
else cut[1]=false;
}
inline void dfs(int x,int fa) {
size[x]=1;
for (edges *i=head[x];i;i=i->last) if (i->v!=fa) {
deep[i->v]=deep[x]+1;
dfs(i->v,x);
fat[i->v]=x;
size[x]+=size[i->v];
if (size[i->v]>size[heavy[x]])
heavy[x]=i->v;
}
}
inline void dfs(int x,int fa,int grand) {
ga[x]=grand;
tid[x]=++dfx;
rid[dfx]=x;
if (heavy[x]) {
dfs(heavy[x],x,grand);
for (edges *i=head[x];i;i=i->last) if (i->v!=fa&&i->v!=heavy[x])
dfs(i->v,x,i->v);
}
}
inline void dfs() {
dfs(1,0);
dfs(1,0,1);
}
}g[2];
struct node {
node (){lc=rc=NULL,val=0;}
node *lc,*rc;
int val;
}tree[N*40],*tcnt=tree,*fina,*root;
inline void update(node *u) {
u->val=u->lc->val+u->rc->val;
}
inline void build (node *&u,int l,int r) {
u=tcnt++;
*u=node();
if (l==r) {
u->val=ncut[rid[l]];
return ;
}
int mid=l+r>>1;
build(u->lc,l,mid);
build(u->rc,mid+1,r);
update(u);
}
inline void update(node *&u,int l,int r,int x,int y) {
if (u<fina) {
node *t=tcnt++;
*t=*u;
u=t;
}
if (x<=l&&r<=y) {u->val=0;return ;}
int mid=l+r>>1;
if (y>mid) update(u->rc,mid+1,r,x,y);
if (x<=mid) update(u->lc,l,mid,x,y);
update(u);
}
inline int query(node *u,int l,int r,int x,int y) {
if (!u->val) return 0;
if (x<=l&&r<=y) return u->val;
int mid=l+r>>1,ret=0;
if (y>mid) ret+=query(u->rc,mid+1,r,x,y);
if (x<=mid) ret+=query(u->lc,l,mid,x,y);
return ret;
}
inline int cmp(int x,int y) {
return tid[x]<tid[y];
}
inline int lca(int x,int y) {
while (ga[x]!=ga[y]) {
if (deep[ga[x]]<deep[ga[y]])
swap(x,y);
x=fat[ga[x]];
}
if (deep[x]<deep[y]) return x;
return y;
}
inline int query(int x,int y) {
int ret=0;
while (ga[x]!=ga[y]) {
if (deep[ga[x]]<deep[ga[y]])
swap(x,y);
ret+=query(root,1,m,tid[ga[x]],tid[x]);
update(root,1,m,tid[ga[x]],tid[x]);
x=fat[ga[x]];
}
if (deep[x]>deep[y]) swap(x,y);
if (tid[x]<=tid[y])
ret+=query(root,1,m,tid[x],tid[y]),
update(root,1,m,tid[x],tid[y]);
return ret;
}
int main (int argc, char const* argv[]){
int T=read();
while (T--){
memset(g,0,sizeof g);
g[0].Clear();
g[1].Clear();
memset(cut,0,sizeof cut);
memset(ncut,0,sizeof ncut);
memset(dfn,0,sizeof dfn);
memset(heavy,0,sizeof heavy);
tcnt=tree;
bcc_cnt=0;
dfx=0,idx=0;
n=read(),m=read();
register int i,j;
for (i=1;i<=m;++i) {
int x=read(),y=read();
g[0].push(x,y);
}
g[0].tarjan();
int s=bcc_cnt;
for (i=1;i<=n;++i)
if (cut[i])
++s,cut[i]=s,ncut[cut[i]]=1;
for (i=1;i<=bcc_cnt;++i) {
for (j=0;j<bcc[i].size();++j)
if (cut[bcc[i][j]])
g[1].push(i,cut[bcc[i][j]]);
else bel[bcc[i][j]]=i;
}
g[1].dfs();
build(root,1,s);
m=s;
fina=tcnt;
int Q=read(),tmp;
int ans=0;
while (Q--) {
root=tree;
tcnt=fina;
s=read();
for (i=1;i<=s;++i) {
pos[i]=read();
if (cut[pos[i]]) pos[i]=cut[pos[i]],update(root,1,m,tid[pos[i]],tid[pos[i]]);
else pos[i]=bel[pos[i]];
}
sort(pos+1,pos+s+1,cmp);
tmp=pos[1];
ans=0;
for (i=2;i<=s;++i) {
ans+=query(tmp,pos[i]);
}
printf("%d\n",ans);
}
}
return 0;
}