• API
• FAQ
• Tools
• Archive
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.

Top