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 
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 ≤ A, B ≤ 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 |
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;
}
Input
1 2 0
2 3 1
3 4 0
Output