fork download
copy 
  1. /// KoJa
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define task "test"
  5. #define pb push_back
  6. #define SZ(a) (a).begin(), (a).end()
  7. #define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
  8. #define BIT(a) (1LL << (a))
  9. #define vec vector
  10. #define fi first
  11. #define se second
  12.  
  13. typedef long long ll;
  14. typedef pair<int, int> ii;
  15.  
  16. template <class T>
  17. inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
  18. template <class T>
  19. inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }
  20. void fastio()
  21. {
  22.     ios_base::sync_with_stdio(NULL);
  23.     cin.tie(NULL);
  24.     if (fopen(task ".inp", "r"))
  25.     {
  26.         freopen(task ".inp", "r", stdin);
  27.         freopen(task ".out", "w", stdout);
  28.     }
  29. }
  30.  
  31. const int N = int(1e6) + 100;
  32. const ll INF = 1e18;
  33. int n, w[N];
  34. struct Edge1
  35. {
  36.     int x, y, w;
  37.     Edge1() {}
  38.     Edge1(int _x, int _y, int _w)
  39.     {
  40.         x = _x;
  41.         y = _y;
  42.         w = _w;
  43.     }
  44.     bool operator<(const Edge1 &b) const
  45.     {
  46.         return (w < b.w);
  47.     }
  48. };
  49. struct Edge2
  50. {
  51.     int x, y, w;
  52.     Edge2() {}
  53.     Edge2(int _x, int _y, int _w)
  54.     {
  55.         x = _x;
  56.         y = _y;
  57.         w = _w;
  58.     }
  59.     bool operator<(const Edge2 &b) const
  60.     {
  61.         return (w > b.w);
  62.     }
  63. };
  64. class DisjointsSet
  65. {
  66. private:
  67.     vec<int> par;
  68.  
  69. public:
  70.     DisjointsSet(int n = 0)
  71.     {
  72.         par.assign(n + 10, -1);
  73.     }
  74.     int root(int u)
  75.     {
  76.         return ((par[u] < 0) ? u : par[u] = root(par[u]));
  77.     }
  78.     bool join(int u, int v)
  79.     {
  80.         u = root(u);
  81.         v = root(v);
  82.         if (u == v)
  83.             return 0;
  84.         if (-par[u] < -par[v])
  85.             swap(u, v);
  86.         par[u] += par[v];
  87.         par[v] = u;
  88.         return 1;
  89.     }
  90.     int getSize(int u)
  91.     {
  92.         return -par[root(u)];
  93.     }
  94. } dsu;
  95. vec<Edge1> edge1;
  96. vec<Edge2> edge2;
  97. void init()
  98. {
  99.     cin >> n;
  100.     for (int i = 1; i <= n; i++)
  101.         cin >> w[i];
  102.     for (int i = 1; i <= n - 1; i++)
  103.     {
  104.         int x, y;
  105.         cin >> x >> y;
  106.         edge1.pb(Edge1(x, y, max(w[x], w[y])));
  107.         edge2.pb(Edge2(x, y, min(w[x], w[y])));
  108.     }
  109. }
  110. ll calcMax()
  111. {
  112.     ll ans = 0;
  113.     dsu = DisjointsSet(n);
  114.     sort(SZ(edge1));
  115.     for (auto e : edge1)
  116.     {
  117.         ans += 1LL * e.w * dsu.getSize(e.x) * dsu.getSize(e.y);
  118.         dsu.join(e.x, e.y);
  119.     }
  120.     return ans;
  121. }
  122. ll calcMin()
  123. {
  124.     ll ans = 0;
  125.     dsu = DisjointsSet(n);
  126.     sort(SZ(edge2));
  127.     for (auto e : edge2)
  128.     {
  129.         ans += 1LL * e.w * dsu.getSize(e.x) * dsu.getSize(e.y);
  130.         dsu.join(e.x, e.y);
  131.     }
  132.     return ans;
  133. }
  134. void process()
  135. {
  136.     cout << calcMax() - calcMin();
  137. }
  138. int main()
  139. {
  140.     fastio();
  141.     init();
  142.     process();
  143.     return 0;
  144. }
  145.  
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jPpii6
language:
C++14 (gcc 8.3)
created:
1 year 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!