51nod_1253:Kundu and Tree（组合数学）

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1253

所有的三元组的可能情况数有ans0=C(n,3)。然后减去不符合条件的情况数。

假设被黑边相连的点形成一个特殊的连通块，在一个大小为x的连通块形成的过程中，ans减去cal(x)=C(x,3)+(n-x)*C(x,2)

代码如下

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=5e4+;

const int mod=;

int fa[N];

LL d[N];

LL ans,n;

int Find(int x)

{

    return x==fa[x]? x:fa[x]=Find(fa[x]);

}

int Union(int x,int y)

{

    x=Find(x);y=Find(y);

    fa[x]=y;

    d[y]+=d[x];

}

void init()

{

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

        fa[i]=i,d[i]=;

}

LL cal(LL x)

{

    return x*(x-)*(x-)/+(n-x)*(x-)*x/;

}

int main()

{

    while(cin>>n)

    {

        init();

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

        {

            int a,b;

            char ch;

            cin>>a>>b>>ch;

            if(ch=='b') Union(a,b);

        }

        ans=n*(n-)*(n-)/;    //ans0=C(n,3)

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

            if(i==fa[i]) ans-=cal(d[i]);

        cout<<ans%mod<<endl;

    }

}

巴特西

51nod_1253:Kundu and Tree（组合数学）

最新文章

热门文章