Advertisement
K_Y_M_bl_C

Untitled

Oct 8th, 2017
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> pii;
  7. typedef vector<int> vi;
  8.  
  9. #define X first
  10. #define Y second
  11. #define inb push_back
  12. #define mk make_pair
  13. #define all(v) v.begin(), v.end()
  14. #define sqr(x) (x) * (x)
  15.  
  16. int solve();
  17.  
  18. int main()
  19. {
  20.     ios_base::sync_with_stdio(0);
  21.     cin.tie(0);
  22.     solve();
  23.     return 0;
  24. }
  25.  
  26. struct item
  27. {
  28.     int x, c;
  29.     item() {};
  30.     item(int x, int c) : x(x), c(c) {};
  31. };
  32.  
  33. const int INF = 1e9 + 7;
  34. const int MAXN = 15e4 + 7;
  35.  
  36. struct SegmentTree
  37. {
  38.     struct Node
  39.     {
  40.         int x, add, id;
  41.         Node() {};
  42.         Node(int x, int add, int id) : x(x), add(add), id(id) {};
  43.     };
  44.     vector<Node> t;
  45.     SegmentTree() { t.resize(600107); };
  46.     Node max(Node &a, Node &b)
  47.     {
  48.         if (a.x > b.x)
  49.             return a;
  50.         return b;
  51.     }
  52.     void push(int v, int tl, int tr)
  53.     {
  54.         if (!t[v].add)
  55.             return;
  56.         t[v].x += t[v].add;
  57.         if (tl != tr)
  58.         {
  59.             t[2 * v + 1].add += t[v].add;
  60.             t[2 * v + 2].add += t[v].add;  
  61.         }
  62.         t[v].add = 0;
  63.     }
  64.     void update(int v, int tl, int tr, int l, int r, int val, int id)
  65.     {
  66.         push(v, tl, tr);
  67.         if (tl > r || tr < l)
  68.             return;
  69.         if (l <= tl && tr <= r)
  70.         {
  71.             t[v].add += val;
  72.             if (id != -1)
  73.                 t[v].id = id;
  74.             push(v, tl, tr);
  75.             return;
  76.         }
  77.         int tm = tl + tr >> 1;
  78.         update(2 * v + 1, tl, tm, l, r, val, id);
  79.         update(2 * v + 2, tm + 1, tr, l, r, val, id);
  80.         t[v] = max(t[2 * v + 1], t[2 * v + 2]);
  81.     }
  82. };
  83.  
  84. int solve()
  85. {
  86.     int n;
  87.     cin >> n;
  88.     vector<vi> g(n);
  89.     int r0 = -1, r1 = -1;
  90.     for (int i = 0; i < n - 1; ++i)
  91.     {
  92.         int x, y;
  93.         cin >> x >> y;
  94.         --x, --y;
  95.         if (!i)
  96.             r0 = x, r1 = y;
  97.         g[x].inb(y);
  98.         g[y].inb(x);
  99.     }
  100.     int m;
  101.     cin >> m;
  102.     vector<vector<item>> q(n);
  103.     int ans = 0;
  104.     for (int i = 0; i < m; ++i)
  105.     {
  106.         int x, y, c;
  107.         cin >> x >> y >> c;
  108.         --x, --y;
  109.         q[x].inb(item(y, c)), q[y].inb(item(x, c));
  110.     }
  111.     vi l(n, INF), r(n);
  112.     vi was(n), was1(n);
  113.     SegmentTree T;
  114.     function<void(int, int, int&, int&)> dfsEU = [&](int u, int pr, int &id, int &sum)
  115.     {
  116.         was[u] = 2;
  117.         was1[u] = 1;
  118.         int add = 0;
  119.         for (auto &x : q[u])
  120.         {
  121.             if (was1[x.x])
  122.                 add += x.c;
  123.         }
  124.         sum += add;
  125.         if (g[u].size() == 1)
  126.         {
  127.             l[u] = id;
  128.             r[u] = id;
  129.             T.update(0, 0, MAXN - 1, id, id, sum, u);
  130.             ++id;
  131.         }
  132.         for (int to : g[u])
  133.         {
  134.             if (to == pr)
  135.                 continue;
  136.             dfsEU(to, u, id, sum);
  137.             l[u] = min(l[u], l[to]);
  138.             r[u] = max(r[u], r[to]);
  139.         }
  140.         //cout << u + 1 << " " << sum << " " << l[u] << " " << r[u] << "\n";
  141.         was1[u] = 0;
  142.         sum -= add;
  143.     };
  144.     int cnt = 0;
  145.     int sum = 0;
  146.     dfsEU(r0, r1, cnt, sum);
  147.     int res = 0, id0 = r0, id1 = r1;
  148.     function<void(int, int, int&)> dfsAns = [&](int u, int pr, int &sum)
  149.     {
  150.         int add = 0;
  151.         was1[u] = 1;
  152.         for (auto &x : q[u])
  153.         {
  154.             if (was1[x.x])
  155.                 add += x.c;
  156.             if (was[x.x] == 2)
  157.                 T.update(0, 0, MAXN - 1, l[x.x], r[x.x], x.c, -1);
  158.         }
  159.         sum += add;
  160.         //cout << u << " " << sum << " " << add << "\n";
  161.         if (T.t[0].x + sum > res)
  162.         {
  163.             id0 = T.t[0].id + 1;
  164.             id1 = u + 1;
  165.             res = sum + T.t[0].x;
  166.         }
  167.         for (int to : g[u])
  168.         {
  169.             if (to == pr)
  170.                 continue;
  171.             dfsAns(to, u, sum);
  172.         }
  173.         sum -= add;
  174.         was1[u] = 0;
  175.         for (auto &x : q[u])
  176.         {
  177.             if (was[x.x] == 2)
  178.                 T.update(0, 0, MAXN - 1, l[x.x], r[x.x], -x.c, -1);
  179.         }
  180.     };
  181.     dfsAns(r1, r0, sum);
  182.     cout << id0 << " " << id1 << " " << res + ans << "\n";
  183.     return 0;
  184. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement