Cerinta completa

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 to b, 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 

5
1 2 b
2 3 r
3 4 r
4 5 b

Sample Output 

4

Explanation

Given tree is something like this.
image

(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.

Limbajul de programare folosit: cpp14

Cod:

#include <iostream>
#include <fstream>
#include <string>
#include <cstdio>
#include <memory.h>
#include <vector>
#include <sstream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <complex>
 
using namespace std;
 
 
#define REP(a,b) for (int a=0; a<(int)(b); ++a)
#define FOR(a,b,c) for (int a=(b); a<(int)(c); ++a)

const int MAXN = 100010;
 
vector <int> tree[MAXN];
char vis[MAXN];

int main() {
    int n, a, b;
    long long res, bad;
    char s[4];
    
    scanf("%d", &n);
    
    REP(i,n-1) {
        scanf("%d%d%s", &a, &b, s);
        if (s[0] == 'b') {
            tree[a-1].push_back(b-1);
            tree[b-1].push_back(a-1);
        }
    }
    
    res = n;
    res = res*(res-1)*(res-2);
    res /= 6;
    
    memset(vis, 0, sizeof(vis));
    
    REP(i,n) if (vis[i] == 0) {
        int v;
        long long cs = 0;
        queue <int> q;
        q.push(i); vis[i] = 1; cs = 1;
        while (!q.empty()) {
            v = q.front(); q.pop();
            REP(j,tree[v].size()) {
                int next = tree[v][j];
                if (vis[next] == 0) {
                    q.push(next);
                    vis[next] = 1;
                    ++cs;
                }
            }
        }
        
        bad = cs*(cs-1)*(n-cs)/2;
        bad += cs*(cs-1)*(cs-2)/6;
        res -= bad;
    }
    
    printf("%d\n", (int)(res%1000000007));

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464653140

Link challenge: https://www.hackerrank.com/challenges/kundu-and-tree/problem

Kundu and Tree