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+5;
const int mod=1000000007;
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=1;i<=n;i++)
        fa[i]=i,d[i]=1;
}

LL cal(LL x)
{
    return x*(x-1)*(x-2)/6+(n-x)*(x-1)*x/2;
}

int main()
{
    while(cin>>n)
    {
        init();
        for(int i=1;i<n;i++)
        {
            int a,b;
            char ch;
            cin>>a>>b>>ch;
            if(ch=='b') Union(a,b);
        }
        ans=n*(n-1)*(n-2)/6;    //ans0=C(n,3)
        for(int i=1;i<=n;i++)
            if(i==fa[i]) ans-=cal(d[i]);
        cout<<ans%mod<<endl;
    }
}