Gym 101142G ： Gangsters in Central City（DFS序+LCA+set）

时间：2021-06-08 07:44:38

题意：现在有一棵树，1号节点是水源，叶子节点是村庄，现在有些怪兽会占领一些村庄（即只占领叶子节点），现在要割去一些边，使得怪兽到不了水源。给出怪兽占领和离开的情况，现在要割每次回答最小的割，使得怪兽不与1号节点有联系，而且满足被阻隔的村庄最少。输出最小割与组少的被误伤的村庄。

思路：把与一号节点相邻的点看作祖先gfa，然后它们自己作为树的根节点，根节点保存了子树里叶子节点的个数。很显然一棵树我们要割的是这棵树里所有怪兽的LCA与父亲边。子数里所有怪兽的LCA=LCA(最小DFS序的怪兽点，最大DFS序的怪兽点)，用set维护有序关系即可。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

vector<int>G[maxn];  set<int>S[maxn];

int dfn[maxn],pos[maxn],fa[maxn][],gfa[maxn],dep[maxn];

int sz[maxn],son[maxn],cut[maxn],num[maxn],times;

void dfs(int u,int f,int two)

{

    dfn[u]=++times; pos[times]=u;  dep[u]=dep[f]+;

    if(dep[u]==) two=u; if(two) gfa[u]=two;

    for(int i=;i<G[u].size();i++)

      if(G[u][i]!=f)

        dfs(G[u][i],u,two),son[u]+=sz[G[u][i]];

    if(!son[u]) sz[u]=;

    else sz[u]=son[u];

}

int LCA(int u,int v){

    if(dep[u]<dep[v]) swap(u,v);

    for(int i=;i>=;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];

    if(u==v) return u;

    for(int i=;i>=;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];

    return fa[u][];

}

int ans1,ans2; int tmp[maxn];

int main()

{

    freopen("gangsters.in","r",stdin);

    freopen("gangsters.out","w",stdout);

    int N,Q,i,j;

    scanf("%d%d",&N,&Q);

    for(i=;i<=N;i++){

        scanf("%d",&fa[i][]);

        G[fa[i][]].push_back(i);

    }

    for(i=;i<=;i++)

     for(j=;j<=N;j++)

      fa[j][i]=fa[fa[j][i-]][i-];

    dfs(,,);

    char opt[]; int x;

    while(Q--){

        scanf("%s%d",opt+,&x);

        int t=gfa[x];

        if(opt[]=='+'){

            if(S[t].empty()) ans1++;

            else ans2-=tmp[t];

            S[t].insert(dfn[x]);

            int Lca=LCA(pos[*S[t].begin()],pos[*S[t].rbegin()]);

            cut[t]=Lca; num[t]++;

            tmp[t]=(sz[cut[t]]-num[t]);

            ans2+=tmp[t];

        }

        else {

            ans2-=tmp[t]; tmp[t]=;

            S[t].erase(dfn[x]); num[t]--;

            if(S[t].empty()) ans1--,cut[t]=;

            else {

                int Lca=LCA(pos[*S[t].begin()],pos[*S[t].rbegin()]);

                cut[t]=Lca; tmp[t]=(sz[cut[t]]-num[t]);

                ans2+=tmp[t];

            }

        }

        printf("%d %d\n",ans1,ans2);

    }

    return ;

}

相关文章