Advertisement
K_Y_M_bl_C

Untitled

Oct 10th, 2017
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 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. #define y1 zapadupal
  16.  
  17. int solve();
  18.  
  19. int main()
  20. {
  21.     ios_base::sync_with_stdio(0);
  22.     cin.tie(0);
  23.     solve();
  24.     return 0;
  25. }
  26.  
  27. struct Query
  28. {
  29.     int l, r, val;
  30.     Query() {};
  31.     Query(int l, int r, int val) : l(l), r(r), val(val) {};
  32. };
  33.  
  34. struct SegmentTree
  35. {
  36.     struct Node
  37.     {
  38.         int x, add, id;
  39.         Node() { x = 0, add = 0, id = 0; };
  40.         Node(int x, int id) : x(x), add(0), id(id) {};
  41.     };
  42.     vector<Node> t;
  43.     SegmentTree() {};
  44.     SegmentTree(int n)
  45.     {
  46.         t.resize(4 * n);
  47.         build(0, 0, n - 1);
  48.     }
  49.     Node max(Node &a, Node &b)
  50.     {
  51.         if (a.x > b.x)
  52.             return a;
  53.         return b;
  54.     }
  55.     void build(int v, int tl, int tr)
  56.     {
  57.         if (tl == tr)
  58.         {
  59.             t[v].id = tl;
  60.             return;
  61.         }
  62.         int tm = tl + tr >> 1;
  63.         build(2 * v + 1, tl, tm);
  64.         build(2 * v + 2, tm + 1, tr);
  65.     }
  66.     void push(int v, int tl, int tr)
  67.     {
  68.         if (!t[v].add)
  69.             return;
  70.         t[v].x += t[v].add;
  71.         if (tl != tr)
  72.         {
  73.             t[2 * v + 1].add += t[v].add;
  74.             t[2 * v + 2].add += t[v].add;
  75.         }
  76.         t[v].add = 0;
  77.     }
  78.     void update(int v, int tl, int tr, int l, int r, int val)
  79.     {
  80.         push(v, tl, tr);
  81.         if (tl > r || tr < l)
  82.             return;
  83.         if (l <= tl && tr <= r)
  84.         {
  85.             t[v].add += val;
  86.             push(v, tl, tr);
  87.             return;
  88.         }
  89.         int tm = tl + tr >> 1;
  90.         update(2 * v + 1, tl, tm, l, r, val);
  91.         update(2 * v + 2, tm + 1, tr, l, r, val);
  92.         t[v] = max(t[2 * v + 1], t[2 * v + 2]);
  93.     }
  94. };
  95.  
  96. int solve()
  97. {
  98.     int n;
  99.     scanf("%d", &n);
  100.     vector<vi> g(n);
  101.     for (int i = 0; i < n - 1; ++i)
  102.     {
  103.         int x, y;
  104.         scanf("%d %d", &x, &y);
  105.         --x, --y;
  106.         g[x].inb(y);
  107.         g[y].inb(x);
  108.     }
  109.     vi tin(n), tout(n);
  110.     vi tr(n);
  111.     vector<vi> sons(n);
  112.     int timer = -1;
  113.     function<void(int, int)> dfs = [&](int u, int pr)
  114.     {
  115.         ++timer;
  116.         tin[u] = timer;
  117.         tr[timer] = u;
  118.         for (int to : g[u])
  119.         {
  120.             if (to == pr)
  121.                 continue;
  122.             sons[u].inb(to);
  123.             dfs(to, u);
  124.         }
  125.         tout[u] = timer;
  126.     };
  127.     dfs(0, -1);
  128.     int m;
  129.     scanf("%d", &m);
  130.     vector<vector<Query>> q(n + 2);
  131.     for (int i = 0; i < m; ++i)
  132.     {
  133.         int x, y, val;
  134.         scanf("%d %d %d", &x, &y, &val);
  135.         --x, --y;
  136.         if (tin[y] <= tin[x] && tin[x] <= tout[y])
  137.             swap(x, y);
  138.         if (tin[x] <= tin[y] && tin[y] <= tout[x])
  139.         {
  140.             int l = 0, r = sons[x].size();
  141.             while (r - l > 1)
  142.             {
  143.                 int mid = l + r >> 1;
  144.                 if (tin[sons[x][mid]] <= y)
  145.                     l = mid;
  146.                 else
  147.                     r = mid;
  148.             }
  149.             int s = sons[x][l];
  150.             //0 <= tin[a] < tin[s]
  151.             //tin[y] <= tin[b] <= tout[y]
  152.             q[0].inb(Query(tin[y], tout[y], val));
  153.             q[tin[s]].inb(Query(tin[y], tout[y], -val));
  154.             //tout[s] < tin[a] <= timer
  155.             //tin[y] <= tin[b] <= tout[y]
  156.             q[tout[s] + 1].inb(Query(tin[y], tout[y], val));
  157.             q[timer + 1].inb(Query(tin[y], tout[y], -val));
  158.         }
  159.         else
  160.         {
  161.             //tin[x] <= tin[a] <= tout[x]
  162.             //tin[y] <= tin[b] <= tout[y]
  163.             q[tin[x]].inb(Query(tin[y], tout[y], val));
  164.             q[tout[x] + 1].inb(Query(tin[y], tout[y], -val));
  165.         }
  166.     }
  167.     int ansx = 0, ansy = 0, ans = 0;
  168.     SegmentTree T(n);
  169.     for (int i = 0; i < n; ++i)
  170.     {
  171.         for (auto &cur : q[i])
  172.         {
  173.             T.update(0, 0, n - 1, cur.l, cur.r, cur.val);
  174.         }
  175.         int id = T.t[0].id;
  176.         int c = T.t[0].x;
  177.         if (c > ans)
  178.             ansx = tr[i] + 1, ansy = id + 1, ans = c;
  179.     }
  180.     printf("%d %d %d\n", ansx, ansy, ans);
  181.     return 0;
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement