fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <utility>
  4.  
  5. using namespace std;
  6.  
  7. pair<int, int> info[100010];
  8. int filhos[100010];
  9. typedef pair<int, int> pii;
  10.  
  11. void make_set(int x){
  12.     info[x]=make_pair(x, 0);
  13.     filhos[x]=1;
  14. }
  15.  
  16. int find_dad(int x){
  17.     if(info[x].first==x) return x;
  18.     else return find_dad(info[x].first);
  19. }
  20.  
  21. void link(int x, int y){
  22.     x=find_dad(x), y=find_dad(y);
  23.     if(info[x].second>info[y].second){
  24.         info[y].first=info[x].first;
  25.         filhos[x]+=filhos[y];
  26.     }else if(info[x].second<info[y].second){
  27.         info[x].first=info[y].first;
  28.         filhos[y]+=filhos[x];
  29.     }else{
  30.         info[x].first=info[y].first;
  31.         info[x].second++;
  32.         filhos[y]+=filhos[x];
  33.     }
  34. }
  35.  
  36. int main( ){
  37.     int n, a, b, c;
  38.     scanf("%d", &n);
  39.     long long int ans=n*(n-1)/2;
  40.     for(int i=1; i<=n; i++) make_set(i);
  41.     for(int i=0; i<n-1; i++){
  42.         scanf("%d %d %d", &a, &b, &c);
  43.         if(c==0) link(a, b);
  44.     }
  45.     for(int i=1; i<=n; i++){
  46.         if(info[i].first==i){
  47.             long long int p=filhos[i];
  48.             ans-=(long long int)p*(p-1)/2;
  49.         }
  50.     }
  51.     printf("%lld", ans);
  52.     return 0;
  53. }
Success #stdin #stdout 0s 4644KB
comments (?)
stdin
copy 
4
1 2 0
2 3 1
3 4 0
stdout
copy 
4
https://ideone.com/SRW4u7
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!