Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2468

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2468

Map

 

By OBI - Olimpíada Brasileira de Informática 2014 BR Brazil

Timelimit: 1

Byteland is a very bustling city, whose mayor, Joãozinho, has recently fighting for his inclusion in the group of the five most important cities of Byteworld. For a city to be considered important in Byteworld, you must follow certain criteria. First of all, let's define Byteland, which is a city like any other, where corners are connected by two-way street. It is also known that there is one and only one path without repeating corners, between any pair of corners. In addition, each street can be considered important or not. If it is important, the street is painted white and if not, is painted blue.

To find out if a city is important or not in Byteworld is necessary to calculate a value E: the amount of corners pairs (A, B) such that there is at least a major street in the path between A and B. Note that (A, B ) and (B, A) are the same pair!

The Mayor of Byteland decided to ask your help to calculate the value E and learn, so if Byteland or not it is an important city for Byteworld.

 

Input

 

The first line of input contains an integer N (2 ≤ N ≤ 105) indicating the number of corners in Byteland. The next N - 1 input lines each contain three integers A, B (1 ≤ AB ≤ N) and C (0 ≤ C ≤ 1), indicating that there is a street between the corners A and B of the painted color C. If C is 1, the road is white and important if 0, the street is blue and unimportant.

 

Output

 

Your program should produce a single line containing a single integer, the value E defined above.

 

 

 

Input Sample Output Sample

4
1 2 0
2 3 1
3 4 0

4

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#define MAXN 100010
typedef long long ll;
ll pai[MAXN], peso[MAXN], filhos[MAXN];
ll resposta;
ll find(ll x) {
    if (x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}
void join(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (peso[x]  <  peso[y]) {
        pai[x] = y;
        filhos[y] += filhos[x];
    } else if (peso[x] > peso[y]) {
        pai[y] = x;
        filhos[x] += filhos[y];
    } else {
        pai[x] = y;
        peso[y]++;
        filhos[y] += filhos[x];
    }
}
int main() {
    ll n;
    scanf("%lld", &n);
    for (ll i = 1; i  < = n; i++) {
        pai[i] = i;
        filhos[i] = 1LL;
    }
    for (ll i = 1; i  <  n; i++) {
        ll u, v, cor;
        scanf("%lld %lld %lld", &u, &v, &cor);
        if (!cor) join(u, v);
    }
    for (ll i = 1; i  < = n; i++) {
        if (pai[i] != i) continue;
        resposta += ((n - filhos[i]) * filhos[i]);
    }
    printf("%lld\n", resposta / 2LL);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
4
1 2 0
2 3 1
3 4 0

Output

x
+
cmd
4
Advertisements

Demonstration


Previous
#2467 Beecrowd Online Judge Solution 2467 Frequency Solution in C, C++, Java, Js and Python
Next
#2469 Beecrowd Online Judge Solution 2469 Grades Solution in C, C++, Java, Js and Python