Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a tob, vertex b to c and vertex c to a . Note that (a,b,c), (b,a,c) and all such permutations will be considered as the same triplet.

If the answer is greater than 109 + 7, print the answer modulo (%) 109 + 7.

Input Format

The first line contains an integer N, i.e., the number of vertices in tree. 

The next N-1 lines represent edges: 2 space separated integers denoting an edge followed by a color of the edge. A color of an edge is denoted by a small letter of English alphabet, and it can be either red(r) or black(b).

Output Format

Print a single number i.e. the number of triplets.

Constraints

1 ≤ N ≤ 105

A node is numbered between 1 to N.

Sample Input

51 2 b2 3 r3 4 r4 5 b

Sample Output

4

Explanation

Given tree is something like this.

(2,3,4) is one such triplet because on all paths i.e 2 to 3, 3 to 4 and 2 to 4 there is atleast one edge having red color.

(2,3,5), (1,3,4) and (1,3,5) are other such triplets. 

Note that (1,2,3) is NOT a triplet, because the path from 1 to 2 does not have an edge with red color.

大体题意：给定一棵树，有两种树边，一种是红色('r'), 另一种是黑色('b'), 在树中找到三个点，使得没两个点之间的路径上都有红色的边，

问存在多少种不同的找法。(a, b, c和 b a c只算一种）

思路：如果有满足要求的３个点ａ，ｂ，ｃ，若把ａ到ｂ中的红色边去掉，那么ａ和ｂ将不连通，同理，如果把ａ到ｂ，ｂ到ｃ，ａ到ｃ中

的红色边都去掉，那么ａ，ｂ，ｃ将属于不同的连通分量。这样就转化为有ｋ堆点，每堆有ａ[i]个，从这ｋ堆中选３个点，并且满足３个点

两两不在同一堆中，问有多少中取法。因此，就有如下方法：

1 long long sum = 0;2 for (int i = 1; i <= k; i++) 3     for (int j = i + 1; j <= k; j++) 4         for (int t = j + 1; t <= k; t++)5             sum += a[i] * a[j] * a[t];

但是复杂度为O(n^3)，显然无法满足题目要求。必须优化到O(n)的复杂度。think about it, how to optimize the solution....???

Accepted Code:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int MOD = 1000000000 + 7; 8 const int MAX_N = 100005; 9 typedef long long LL;10 vector
         
           G[MAX_N];11 int N, cmp[MAX_N];12 LL cnt[MAX_N], A[MAX_N], B[MAX_N], C[MAX_N];13 bool vis[MAX_N];14 15 void dfs(int u, int k) {16     cmp[u] = k; vis[u] = true;17     for (int i = 0; i < G[u].size(); i++) {18         int v = G[u][i];19         if (!vis[v]) dfs(v, k); 20     }21 }22 int main(void) { 23      while (cin >> N) { 24          for (int i = 1; i <= N; i++) G[i].clear(); 25          for (int i = 0; i < N; i++) { 26              int a, b; char c; cin >> a >> b >> c; 27              if (c != 'r') G[a].push_back(b), G[b].push_back(a);28         }29         memset(vis, false, sizeof(vis));30         int k = 1; //连通分量个数31         for (int i = 1; i <= N; i++) if (!vis[i]) dfs(i, k++);32         k--;33         memset(cnt, 0, sizeof(cnt));　//每个连通分量点的个数34         for (int i = 1; i <= N; i++) cnt[cmp[i]]++; 35         A[k] = cnt[k];　//A[i] = cnt[i] + cnt[i + 1] + ... + cnt[k]36         for (int i = k - 1; i >= 3; i--) A[i] = (A[i + 1] + cnt[i]) % MOD;37         for (int i = 2; i < k; i++) B[i] = (cnt[i] * A[i + 1]) % MOD; //B[i] = cnt[i] * A[i + 1].38         C[k - 1] = B[k - 1]; //C[i] = B[i] + B[i + 1] + ... + B[k - 1]39         for (int i = k - 2; i >= 2; i--) C[i] = (C[i + 1] + B[i]) % MOD;40         LL sum = 0;41         for (int i = 1; i <= k - 2; i++) sum = (sum + cnt[i] * C[i + 1]) % MOD;42         cout << sum << endl;43     }44     return 0;45 }