# Kundu and Tree

### Problem Statement :

```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```

### Solution :

```                            ```Solution in C :

In C ++ :

#define NDEBUG
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define repeat(n) for (int repc = (n); repc > 0; --repc)
typedef long long int64;

struct UnionFind {
int n;

UnionFind(int n) : n(n) {
rank.resize(n);
size.resize(n);
reset();
}

void reset() {
for (int i=0; i<n; ++i) {
}
fill(rank.begin(), rank.end(), 0);
fill(size.begin(), size.end(), 1);
}

int find(int a) {
int top;
while (a != top) { int x = dad[a]; dad[a] = top; a = x; }
}

int union_find(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (rank[a] > rank[b]) {
size[a] += size[b];
} else {
size[b] += size[a];
if (rank[a] == rank[b]) {
++rank[b];
}
}
return 1;
}
return 0;
}
};

int main() {
ios_base::sync_with_stdio(0);

int n;
cin >> n;

UnionFind uf(n);
repeat (n-1) {
int a, b;
char ch;
cin >> a >> b >> ws >> ch;
if (ch == 'b') {
uf.union_find(a-1, b-1);
}
}

auto choose3 = [](int x) { return int64(x) * (x-1) * (x-2) / 6; };
auto choose2 = [](int x) { return int64(x) * (x-1) / 2; };

int64 ans = choose3(n);
for (int i=0; i<n; ++i) {
if (uf.find(i) == i) {
int c = uf.size[i];
ans -= choose3(c);
ans -= choose2(c) * (n-c);
}
}
cout << ans % 1000000007 << '\n';
return 0;
}

In  Java :

import java.io.*;
import java.util.ArrayList;

public class Solution {

public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
ArrayList<Integer>[] edges = new ArrayList[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<Integer>();
}
for (int i = 0; i < n - 1; ++i) {
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
if (in.next().equals("b")) {
}
}
boolean[] col = new boolean[n];
long c1 = 0, c2 = 0, c3 = 0;
for (int i = 0; i < n; ++i) {
if (!col[i]) {
int c = dfs(i, edges, col);
c3 += c * c2;
c2 += c * c1;
c1 += c;
}
}
out.println(c3 % 1000000007);
}

private static int dfs(int i, ArrayList<Integer>[] edges, boolean[] col) {
if (col[i]) {
return 0;
}
col[i] = true;
int r = 1;
for (int j : edges[i]) {
r += dfs(j, edges, col);
}
return r;
}

public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
out.close();
}

static class Input {
StringBuilder sb = new StringBuilder();

this.in = in;
}

public Input(String s) {
}

public String next() throws IOException {
sb.setLength(0);
while (true) {
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}

public int nextInt() throws IOException {
return Integer.parseInt(next());
}

public long nextLong() throws IOException {
return Long.parseLong(next());
}

public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}

In C :

#include<stdio.h>
#include<stdlib.h>
#define mod 1000000007
#define ll long long
ll nodes[100005],hash[100005],sz[100005];

ll root(ll i)
{
while(i!=nodes[i])i=nodes[i];
return i;
}
void unon_ins(ll p,ll q)
{
ll i,j;
i=root(p);
j=root(q);
if(sz[i]<sz[j]){nodes[i]=j;sz[i]+=sz[j];}
else{nodes[j]=i;sz[j]+=sz[i];}
}

int main()
{

long long res,prod1,prod2,sum=0;
ll n,i,j,k,n_b=0;
char ch;
for(i=0;i<100005;i++)
nodes[i]=i;
scanf("%lld",&n);
for(i=1;i<n;i++)
{
ll x,y;
scanf("%lld %lld %c",&x,&y,&ch);
//printf("%d %d %c\n",x,y,ch);
if(ch=='b')
{
unon_ins(x,y);
n_b++;
}
}
if(((n-1)-n_b)>=2){

for(i=1;i<=n;i++)
hash[root(nodes[i])]++;

res=((n*(n-1)/2)*(n-2))/3;
for(i=1;i<=n;i++)
{
long long t=hash[i];
prod1=prod2=0;
prod1=((t*(t-1))/2)*(3*n-2*t-2)/3;
sum=(sum+prod1);
}
res=(res-sum);

printf("%lld\n",res%mod);}
else
printf("0\n");
return 0;
}

In Python3 :

n = int(input())

p = list(range(n))
rank = [0] * n
size = [1] * n

def get(v):
stack = []
while p[v] != v:
stack.append(v)
v = p[v]
for u in stack:
p[u] = v
return v

def union(v1, v2):
v1 = get(v1)
v2 = get(v2)
if v1 == v2:
return
if rank[v1] < rank[v2]:
v1, v2 = v2, v1
size[v1] += size[v2]
p[v2] = v1
rank[v1] += 1

for _ in range(n - 1):
x, y, col = input().split()
if col == 'b':
union(int(x) - 1, int(y) - 1)

a = [size[i] for i in range(n) if p[i] == i]

MOD = 10**9 + 7
def solve(a):
s1 = [0]
for x in a:
s1.append((s1[-1] + x) % MOD)
s2 = [0]
for i, x in enumerate(a):
s2.append((s2[-1] + x * s1[i]) % MOD)
s3 = [0]
for i, x in enumerate(a):
s3.append((s3[-1] + x * s2[i]) % MOD)
return s3[-1]

print(solve(a))```
```

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element