正题

题目链接:https://www.luogu.com.cn/problem/P4606

题目大意

给出\(n\)个点\(m\)条边的一张图，\(q\)次询问给出一个点集，询问有多少个点割掉后可以是点集中至少一个点对不连通。

解题思路

就是问圆方树上的虚树中的圆点数量，照着统计就好了。

细节有点多，注意不要习惯性的把根节点带进虚树就好了。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<stack>

using namespace std;

const int N=2e5+10;

int T,n,m,q,dfc,cnt,ans,p[N],dfn[N],low[N],s[N];

int pn,dis[N],dep[N],fa[N],top[N],siz[N],son[N];

vector<int> G[N],H[N];stack<int> S;

void tarjan(int x){

    dfn[x]=low[x]=++dfc;S.push(x);

    for(int i=0;i<H[x].size();i++){

        int y=H[x][i];

        if(!dfn[y]){

            tarjan(y);

            low[x]=min(low[x],low[y]);

            if(low[y]==dfn[x]){

                int k;++n;

                do{

                    k=S.top();S.pop();

                    G[n].push_back(k);

                    G[k].push_back(n);

                }while(k!=y);

                G[n].push_back(x);

                G[x].push_back(n);

            }

        }

        else low[x]=min(low[x],dfn[y]);

    }

    return;

}

void dfs1(int x){

    dfn[x]=++dfc;siz[x]=1;

    dep[x]=dep[fa[x]]+1;

    dis[x]=dis[fa[x]]+(x<=pn);

    for(int i=0;i<G[x].size();i++){

        int y=G[x][i];

        if(y==fa[x])continue;

        fa[y]=x;dfs1(y);siz[x]+=siz[y];

        if(siz[y]>siz[son[x]])son[x]=y;

    }

    return;

}

void dfs2(int x){

    if(son[x]){

        top[son[x]]=top[x];

        dfs2(son[x]);

    }

    for(int i=0;i<G[x].size();i++){

        int y=G[x][i];

        if(y==fa[x]||y==son[x])continue;

        top[y]=y;dfs2(y);

    }

    return;

}

int LCA(int x,int y){

    while(top[x]!=top[y]){

        if(dep[top[x]]<dep[top[y]])swap(x,y);

        x=fa[top[x]];

    }

    return (dep[x]<dep[y])?x:y;

}

void Add(int x){

    if(!cnt){s[++cnt]=x;return;}

    int lca=LCA(x,s[cnt]);

    while(cnt>1&&dep[s[cnt-1]]>dep[lca])

        ans+=dis[s[cnt]]-dis[s[cnt-1]],cnt--;

    if(dep[s[cnt]]>dep[lca])

        ans+=dis[s[cnt]]-dis[lca],cnt--;

    if(s[cnt]!=lca)s[++cnt]=lca;

    s[++cnt]=x;return;

}

bool cmp(int x,int y)

{return dfn[x]<dfn[y];}

int main()

{

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);dfc=0;pn=n;

        for(int i=1;i<=2*n;i++)

            H[i].clear(),G[i].clear(),dfn[i]=low[i]=son[i]=0;

        for(int i=1;i<=m;i++){

            int x,y;

            scanf("%d%d",&x,&y);

            H[x].push_back(y);

            H[y].push_back(x);

        }

        tarjan(1);dfc=0;

        dfs1(1);top[1]=1;dfs2(1);

        scanf("%d",&q);

        while(q--){

            scanf("%d",&m);

            for(int i=1;i<=m;i++)scanf("%d",&p[i]);

            sort(p+1,p+1+m,cmp);cnt=ans=0;

            // if(p[1]!=1)s[++cnt]=1;

            for(int i=1;i<=m;i++)

                Add(p[i]);

            while(cnt>1)ans+=dis[s[cnt]]-dis[s[cnt-1]],cnt--;

            printf("%d\n",ans-m+(LCA(p[1],p[m])<=pn));

        }

    }

    return 0;

}

巴特西

P4606-[SDOI2018]战略游戏【圆方树,虚树】

正题

题目大意

解题思路

code

最新文章

热门文章