III.[SDOI2018]战略游戏
这题我居然能1A,神奇,神奇
本题是老缝合怪了,强行把一个圆方树板子跟一个虚树板子缝到了一起。不会虚树的可以参见笔者的虚树学习笔记。
具体来说,首先我们先建出圆方树出来;然后,再在圆方树上针对给定的点集跑出虚树出来;然后,对圆方树上的圆点数量做一个树上前缀和(本题只能删圆点,不能删方点),在虚树上每一条边用儿子的前缀和减去父亲的前缀和即可。注意到如果虚树中的虚点(即LCA节点)是圆点的话,则它也是可以被删去的,应该被计入答案。
代码(namespace
套namespace
真有意思):
#include<bits/stdc++.h>
using namespace std;
int T,n,m,q,c;
namespace Tree{
int dep[200100],sum[200100],anc[200100][20],dfn[200100],tot;
namespace real{
vector<int>v[200100];
void ae(int x,int y){v[x].push_back(y),v[y].push_back(x);}
void dfs(int x,int fa){
sum[x]=sum[fa]+(x<=n),anc[x][0]=fa,dep[x]=dep[fa]+1,dfn[x]=++tot;
for(int i=1;i<=19;i++)anc[x][i]=anc[anc[x][i-1]][i-1];
for(auto y:v[x])if(y!=fa)dfs(y,x);
}
}
int LCA(int x,int y){
if(dep[x]>dep[y])swap(x,y);
for(int i=19;i>=0;i--)if(dep[x]<=dep[y]-(1<<i))y=anc[y][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
namespace imag{
int a[100100],stk[200100],tp,sz[200100],all,res;
bool marked[200100];
vector<int>v[200100];
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void ae(int x,int y){v[x].push_back(y);}
void ins(int x){
marked[x]=true,sz[x]=1;
if(!tp){stk[++tp]=x;return;}
int lca=LCA(x,stk[tp]);
while(tp>=2&&dep[stk[tp-1]]>dep[lca])ae(stk[tp-1],stk[tp]),tp--;
if(tp&&dep[stk[tp]]>dep[lca])ae(lca,stk[tp--]);
if(!tp||stk[tp]!=lca)stk[++tp]=lca;
stk[++tp]=x;
}
void fin(){
while(tp>=2)ae(stk[tp-1],stk[tp]),tp--;
tp--;
}
void dfs1(int x){
int msz=0;
for(auto y:v[x]){
dfs1(y);
if(sz[y]<all)res+=sum[anc[y][0]]-sum[x];
sz[x]+=sz[y],msz=max(msz,sz[y]);
}
if(!marked[x]&&msz<sz[x]&&x<=n)res++;
}
void dfs2(int x){
sz[x]=marked[x]=0;
for(auto y:v[x])dfs2(y);
v[x].clear();
}
int work(){
scanf("%d",&all),res=0;
for(int i=1;i<=all;i++)scanf("%d",&a[i]);
sort(a+1,a+all+1,cmp);
if(a[1]!=1)stk[tp=1]=1;
for(int i=1;i<=all;i++)ins(a[i]);
fin();
dfs1(1),dfs2(1);
return res;
}
}
}
namespace Graph{
vector<int>v[100100];
int dfn[100100],low[100100],tot;
stack<int>s;
void Tarjan(int x){
dfn[x]=low[x]=++tot,s.push(x);
for(auto y:v[x]){
if(!dfn[y]){
Tarjan(y),low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
Tree::real::v[++c].clear();
while(s.top()!=y)Tree::real::ae(c,s.top()),s.pop();
Tree::real::ae(c,s.top()),s.pop();
Tree::real::ae(c,x);
}
}else low[x]=min(low[x],dfn[y]);
}
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m),c=n,Graph::tot=Tree::tot=0;
for(int i=1;i<=n;i++)Graph::v[i].clear(),Tree::real::v[i].clear(),Graph::dfn[i]=Graph::low[i]=0;
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),Graph::v[x].push_back(y),Graph::v[y].push_back(x);
Graph::Tarjan(1),Graph::s.pop();
Tree::real::dfs(1,0);
scanf("%d",&q);
while(q--)printf("%d\n",Tree::imag::work());
}
return 0;
}