0-1-Tree CodeForces – CF1156D(并查集应用)

题目链接

https://codeforces.com/contest/1156/problem/D

题目大意

有一颗树,边权不是零就是一,如果走了边权为1的边后就不能再走边权为0的了。
问有多少种走法。

解题思路

并查集维护与这个点相连的通过边权为0相连的点数与通过1相连的点数。
最后遍历每个点,累加三种走法(0-1,1-1,0-1)的结果即可,详见代码注释。

代码

#include <bits/stdc++.h>
const int maxn=212345;
using namespace std;
int fa[2][maxn],siz[2][maxn];
int root(int x,int z)
{
    if(fa[z][x]==x)
        return x;
    else return fa[z][x]=root(fa[z][x],z);
}
void zhan(int x,int y,int z)
{
    x=root(x,z);
    y=root(y,z);
    fa[z][y]=x;
    siz[z][x]+=siz[z][y];
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        fa[0][i]=fa[1][i]=i;
        siz[0][i]=siz[1][i]=1;
    }
    for(int i=0;i<n-1;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        zhan(u,v,w);
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        if(fa[0][i]==i)//当前节点作为0的起始点到0
            ans+=siz[0][i]*1ll*(siz[0][i]-1);
        if(fa[1][i]==i)//当前节点作为1的起始点到1
            ans+=siz[1][i]*1ll*(siz[1][i]-1);
        //从0到1途径i
        ans+=(siz[0][root(i,0)]-1)*1ll*(siz[1][root(i,1)]-1);
    }
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注