Advertisement
K_Y_M_bl_C

Untitled

Oct 10th, 2017
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.31 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.     function<void(int, int, int, int, int)> add_rect = [&](int x, int y, int x1, int y1, int val)
  132.     {
  133.         q[x].inb(Query(x1, y1, val));
  134.         q[y + 1].inb(Query(x1, y1, -val));
  135.         q[x1].inb(Query(x, y, val));
  136.         q[y1 + 1].inb(Query(x, y, -val));
  137.     };
  138.     for (int i = 0; i < m; ++i)
  139.     {
  140.         int x, y, val;
  141.         scanf("%d %d %d", &x, &y, &val);
  142.         --x, --y;
  143.         if (tin[y] <= tin[x] && tin[x] <= tout[y])
  144.             swap(x, y);
  145.         if (tin[x] <= tin[y] && tin[y] <= tout[x])
  146.         {
  147.             int l = 0, r = sons[x].size();
  148.             while (r - l > 1)
  149.             {
  150.                 int mid = l + r >> 1;
  151.                 if (tin[sons[x][mid]] <= y)
  152.                     l = mid;
  153.                 else
  154.                     r = mid;
  155.             }
  156.             int s = sons[x][l];
  157.             //0 <= tin[a] < tin[s]
  158.             //tin[y] <= tin[b] <= tout[y]
  159.             add_rect(0, tin[s] - 1, tin[y], tout[y], val);
  160.             //tout[s] < tin[a] <= timer
  161.             //tin[y] <= tin[b] <= tout[y]
  162.             add_rect(tout[s] + 1, timer, tin[y], tout[y], val);
  163.         }
  164.         else
  165.         {
  166.             //tin[x] <= tin[a] <= tout[x]
  167.             //tin[y] <= tin[b] <= tout[y]
  168.             add_rect(tin[x], tout[x], tin[y], tout[y], val);
  169.         }
  170.     }
  171.     int ansx = 0, ansy = 0, ans = 0;
  172.     SegmentTree T(n);
  173.     for (int i = 0; i < n; ++i)
  174.     {
  175.         for (auto &cur : q[i])
  176.         {
  177.             T.update(0, 0, n - 1, cur.l, cur.r, cur.val);
  178.         }
  179.         int id = T.t[0].id;
  180.         int c = T.t[0].x;
  181.         if (c > ans)
  182.             ansx = tr[i] + 1, ansy = id + 1, ans = c;
  183.     }
  184.     printf("%d %d %d\n", ansx, ansy, ans);
  185.     return 0;
  186. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement