题目链接：

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

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

代码如下

#include
     
      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
      
       >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<
       
        <