bzoj5315/luoguP4517 [SDOI2018]战略游戏(圆方树，虚树)
题目描述略(太长了)
题解时间
切掉一个点，连通性变化。
上圆方树。
$ sum |S| $ 。
上虚树。
就是将圆方树构建好后每次询问一个连通块的圆点个数。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
template<typename TP>inline void read(TP &tar)
{
TP ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
tar=ret*f;
}
namespace RKK
{
const int N=200011;
int log[N];
struct sumireko{int to,ne;}e[N<<1];int he[N],ecnt;
void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f];he[f]=ecnt;}
int TAT,n,nn,m,qaq;
int lst[N],ln,lk;
int sta[N],stp;
int dfn[N],low[N],da;
vector<int>to[N];
void tj(int x,int f)
{
dfn[x]=low[x]=++da,sta[++stp]=x;
for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
{
if(!dfn[t])
{
tj(t,x),low[x]=min(low[x],low[t]);
if(low[t]>=dfn[x])
{
nn++;int px=0;
while(px!=t)
{
px=sta[stp--];
to[nn].push_back(px);
to[px].push_back(nn);
}
px=x;
to[nn].push_back(px);
to[px].push_back(nn);
}
}else if(t!=f) low[x]=min(low[x],dfn[t]);
}
}
int fa[N][20],sz[N],sp[N],ep[N],dep[N];
void dfs(int x)
{
sp[x]=++da;
for(int k=1;k<=log[dep[x]];k++) fa[x][k]=fa[fa[x][k-1]][k-1];
sz[x]+=(x<=n);int t;
vector<int>::iterator it;
for(it=to[x].begin();it!=to[x].end();it++)
{
t=*it;if(t==fa[x][0]) continue;
sz[t]=sz[x],fa[t][0]=x,dep[t]=dep[x]+1,dfs(t);
}
ep[x]=da;
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int k=log[dep[x]-dep[y]];k>=0;k--)
if((1<<k)<=dep[x]-dep[y]) x=fa[x][k];
for(int k=log[dep[x]];k>=0;k--)
if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
return x==y?x:fa[x][0];
}
bool cmp(const int &a,const int &b){return sp[a]<sp[b];}
int ans;
void add(int anc,int x){ans+=sz[x]-sz[anc];}
void solve()
{
stp=0,ans=0;
read(lk),ln=lk;
for(int i=1;i<=ln;i++) read(lst[i]);
sort(lst+1,lst+1+ln,cmp);
for(int i=1,lim=ln;i<lim;i++) lst[++ln]=lca(lst[i],lst[i+1]);
sort(lst+1,lst+1+ln,cmp),ln=unique(lst+1,lst+1+ln)-lst-1;
ans+=lst[1]<=n;
for(int i=1;i<=ln;i++)
{
while(stp&&ep[sta[stp]]<sp[lst[i]]) stp--;
if(stp) add(sta[stp],lst[i]);sta[++stp]=lst[i];
}
ans-=lk;
printf("%d
",ans);
}
void memclr()
{
memset(he,0,sizeof(he)),ecnt=0;
memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low));
memset(fa,0,sizeof(fa));
for(int i=1;i<=nn;i++) to[i].clear();
}
int Iris()
{
for(int i=2;i<=200000;i++) log[i]=log[i>>1]+1;
read(TAT);while(TAT--)
{
read(n),read(m),nn=n;for(int i=1,x,y;i<=m;i++) read(x),read(y),addline(x,y),addline(y,x);
tj(1,0);
da=0,dfs(1);
read(qaq);
while(qaq--)
solve();
memclr();
}
return 0;
}
}
int main(){return RKK::Iris();}