【枚举】【DFS序】Gym - 101617G

题意：一颗树，每条边有个颜色，一条路径被定义为“彩虹”，当且仅当其上没有长度大于等于2的同色子路径。一个结点被定义为“超级结点”，当且仅当从其发出的所有路径都是“彩虹”。

枚举所有长度为2，且同色的路径，其两端点方向发出的子树中的结点都不可能成为答案，只需要将它们覆盖掉即可，用dfs序处理，在左端点+1，右端点-1，最后求个前缀和，为0的结点就是没有被覆盖过的结点，也即“超级结点”。

分两种情况：这两条边深度相同；这两条边深度不同。

#include<cstdio>

#include<map>

#include<vector>

#include<algorithm>

using namespace std;

int n;

int c[50005],Map[50005];

int fa[50005],first[50005],nex[100005],v[100005],e,Ls[50005],Rs[50005],tot,w[100005];

int fav[50005];

void AddEdge(int U,int V,int W){

    v[++e]=V;

    w[e]=W;

    nex[e]=first[U];

    first[U]=e;

}

void df1(int U){

    Ls[U]=++tot;

    Map[tot]=U;

    for(int i=first[U];i;i=nex[i]){

        if(!fa[v[i]]){

            fa[v[i]]=U;

            fav[v[i]]=w[i];

            df1(v[i]);

        }

    }

    Rs[U]=tot;

}

void fugai(int L,int R){

    ++c[L];

    if(R!=n){

        --c[R+1];

    }

}

void fugai2(int L,int R){

    if(L!=1){

        ++c[1];

        --c[L];

    }

    if(R!=n){

        ++c[R+1];

    }

}

void dfs(int U){

    for(int i=first[U];i;i=nex[i]){

        if(fa[v[i]]==U){

            if(U!=1 && fav[U]==w[i]){

                fugai(Ls[v[i]],Rs[v[i]]);

                fugai2(Ls[U],Rs[U]);

            }

            dfs(v[i]);

        }

    }

}

void df2(int U){

    map<int,int>cnts;

    for(int i=first[U];i;i=nex[i]){

        if(fa[v[i]]==U){

            ++cnts[w[i]];

        }

    }

    for(int i=first[U];i;i=nex[i]){

        if(fa[v[i]]==U){

            if(cnts[w[i]]>1){

                fugai(Ls[v[i]],Rs[v[i]]);

            }

            df2(v[i]);

        }

    }

}

int main(){

    //freopen("g.in","r",stdin);

    scanf("%d",&n);

    int x,y,z;

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

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

        AddEdge(x,y,z);

        AddEdge(y,x,z);

    }

    fa[1]=-1;

    df1(1);

    dfs(1);

    df2(1);

    vector<int>vs;

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

        c[i]+=c[i-1];

        //printf("%d ",c[i]);

        if(!c[i]){

            vs.push_back(Map[i]);

        }

    }

    //puts("");

    printf("%d\n",vs.size());

    sort(vs.begin(),vs.end());

    for(vector<int>::iterator it=vs.begin();it!=vs.end();++it){

        printf("%d\n",*it);

    }

    return 0;

}

巴特西

【枚举】【DFS序】Gym - 101617G - Rainbow Roads

最新文章

热门文章