SHARE
TWEET

Untitled

a guest Aug 20th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // OBI 2014 - 2nd Stage - Mapa
  2. // Lúcio Cardoso
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5+10;
  9.  
  10. int pai[maxn], peso[maxn];
  11.  
  12. bool mark[maxn];
  13.  
  14. int Find(int x)
  15. {
  16.     if (pai[x] == x) return x;
  17.     return pai[x] = Find(pai[x]);
  18. }
  19.  
  20. void Join(int x, int y)
  21. {
  22.     x = Find(x), y = Find(y);
  23.     if (x == y) return;
  24.  
  25.     if (peso[x] < peso[y]) swap(x, y);
  26.  
  27.     pai[y] = x, peso[x] += peso[y];
  28. }
  29.  
  30. int main(void)
  31. {
  32.     int n;
  33.     scanf("%d", &n);
  34.  
  35.     for (int i = 1; i <= n; i++)
  36.         pai[i] = i, peso[i] = 1;
  37.  
  38.     for (int i = 1; i < n; i++)
  39.     {
  40.         int u, v, w;
  41.         scanf("%d %d %d", &u, &v, &w);
  42.  
  43.         if (!w) Join(u, v);
  44.     }
  45.        
  46.     vector<int> comp;
  47.  
  48.     for (int i = 1; i <= n; i++)
  49.     {
  50.         if (!mark[Find(i)])
  51.         {
  52.             mark[Find(i)] = true;
  53.             comp.push_back(peso[Find(i)]);
  54.         }
  55.     }
  56.  
  57.     int tot = n;
  58.     long long ans = 0;
  59.  
  60.     for (auto c: comp)
  61.     {
  62.         ans += 1ll*c*(tot-c);
  63.         tot -= c;
  64.     }
  65.  
  66.     printf("%lld\n", ans);
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top