51Nod1253 Kundu and Tree 容斥原理

​​題目傳送門 - 51Nod1253​​題意

　　樹包含 N 個點和 N-1 條邊。樹的邊有 2 中顔色紅色 ('r') 和黑色 ('b') 。給出這 N-1 條邊的顔色，求有多少節點的三元組 (a,b,c) 滿足：節點 a 到節點 b 、節點 b 到節點 c 、節點 c 到節點 a 的路徑上，每條路徑都至少有一條邊是紅色的。注意 (a,b,c) , (b,a,c) 以及所有其他排列被認為是相同的三元組。輸出結果對 1000000007 取餘的結果。

題解

　　把黑色邊連接配接的點搞成一塊。

　　答案 = 任選 3 個點的方案數 - 在同一個黑色塊中選 3 個點的方案數 - 任選三個數，其中兩個點在同一個黑色塊中的方案數。

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=50005;
int read(){
  int x=0;
  char ch=getchar();
  while (!isdigit(ch))
    ch=getchar();
  while (isdigit(ch))
    x=(x<<1)+(x<<3)+ch-48,ch=getchar();
  return x;
}
struct Gragh{
  static const int M=N*2;
  int cnt,y[M],z[M],nxt[M],fst[N];
  void clear(){
    cnt=0;
    memset(fst,0,sizeof fst);
  }
  void add(int a,int b,int c){
    y[++cnt]=b,z[cnt]=c,nxt[cnt]=fst[a],fst[a]=cnt;
  }
}g;
int n,dsize[N];
vector <int> sz;
void dfs(int x,int pre){
  dsize[x]=1;
  for (int i=g.fst[x];i;i=g.nxt[i])
    if (g.y[i]!=pre){
      int y=g.y[i];
      dfs(y,x);
      if (g.z[i])
        dsize[x]+=dsize[y];
      else
        sz.push_back(dsize[y]);
    }
}
LL calc(LL x){
  return x*(x-1)*(x-2)/6;
}
int main(){
  n=read();
  for (int i=1;i<n;i++){
    int x=read(),y=read();
    char s[2];
    scanf("%s",s);
    g.add(x,y,s[0]=='b');
    g.add(y,x,s[0]=='b');
  }
  sz.clear();
  dfs(1,0);
  sz.push_back(dsize[1]);
  LL ans=calc(n);
  for (int i=0;i<sz.size();i++)
    ans-=calc(sz[i])+1LL*sz[i]*(sz[i]-1)/2*(n-sz[i]);
  printf("%lld",ans%1000000007);
  return 0;
}