Advertisement
K_Y_M_bl_C

Untitled

Sep 18th, 2017
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.35 KB | None | 0 0
  1. //#define _GLIBCXX_DEBUG
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef vector<int> vi;
  10. typedef long double ld;
  11.  
  12. #define mk make_pair
  13. #define inb push_back
  14. #define X first
  15. #define Y second
  16. #define all(v) v.begin(), v.end()
  17. #define sqr(x) (x) * (x)
  18. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  19. #define y1 AYDARBOG
  20. //continue break pop_back return
  21.  
  22. int solve();
  23.  
  24. int main()
  25. {
  26.     //ios_base::sync_with_stdio(0);
  27.     //cin.tie(0);
  28. #define TASK "hypercube"
  29. #ifndef _DEBUG
  30.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  31. #endif
  32.     solve();
  33. #ifdef _DEBUG
  34.     fprintf(stderr, "\nTIME: %.3f\n", TIME);
  35. #endif
  36. }
  37.  
  38. const int BUFSZ = (int)1e5 + 7;
  39. char buf[BUFSZ];
  40. string get_str()
  41. {
  42.     scanf(" %s", buf);
  43.     return string(buf);
  44. }
  45.  
  46. int rand32()
  47. {
  48.     return (rand() << 15) ^ rand();
  49. }
  50.  
  51. struct Node
  52. {
  53.     int x, y, sz;
  54.     ll sum;
  55.     Node *l, *r;
  56.     Node() {};
  57.     Node(int val)
  58.     {
  59.         x = sum = val;
  60.         sz = 1;
  61.         y = rand32();
  62.         l = r = nullptr;
  63.     }
  64.     void print()
  65.     {
  66.         printf("%d %d %lld\n", x, sz, sum);
  67.     }
  68. };
  69.  
  70. int getsz(Node *t)
  71. {
  72.     if (!t)
  73.         return 0;
  74.     return t->sz;
  75. }
  76.  
  77. ll getsum(Node *t)
  78. {
  79.     if (!t)
  80.         return 0;
  81.     return t->sum;
  82. }
  83.  
  84. void update(Node *&t)
  85. {
  86.     if (!t)
  87.         return;
  88.     t->sz = getsz(t->l) + getsz(t->r) + 1;
  89.     t->sum = getsum(t->l) + getsum(t->r) + t->x;
  90. }
  91.  
  92. Node *root = nullptr;
  93.  
  94. void split(Node *root, Node *&left, Node *&right, int x)
  95. {
  96.     if (!root)
  97.     {
  98.         left = right = nullptr;
  99.         return;
  100.     }
  101.     if (root->x < x)
  102.     {
  103.         split(root->r, root->r, right, x);
  104.         left = root;
  105.     }
  106.     else
  107.     {
  108.         split(root->l, left, root->l, x);
  109.         right = root;
  110.     }
  111.     update(left);
  112.     update(right);
  113.     update(root);
  114. }
  115.  
  116. void merge(Node *&t, Node *left, Node *right)
  117. {
  118.     if (!left || !right)
  119.     {
  120.         t = !right ? left : right;
  121.         return;
  122.     }
  123.     if (left->y > right->y)
  124.     {
  125.         merge(left->r, left->r, right);
  126.         t = left;
  127.     }
  128.     else
  129.     {
  130.         merge(right->l, left, right->l);
  131.         t = right;
  132.     }
  133.     update(left);
  134.     update(right);
  135.     update(t);
  136. }
  137.  
  138. void printdd(Node *cur)
  139. {
  140.     if (!cur)
  141.         return;
  142.     printdd(cur->l);
  143.     printf("%d ", cur->x);
  144.     printdd(cur->r);
  145. }
  146.  
  147. bool checkfind(Node *&t, int x)
  148. {
  149.     if (!t)
  150.         return 0;
  151.     if (t->x == x)
  152.         return 1;
  153.     if (t->x > x)
  154.         return checkfind(t->l, x);
  155.     return checkfind(t->r, x);
  156. }
  157.  
  158. void insert(Node *&t0, Node *&t1, int x)
  159. {
  160.     if (checkfind(t0, x) || checkfind(t1, x))
  161.         return;
  162.     Node *cur = new Node(x);
  163.     Node *t0l, *t0r, *t1l, *t1r;
  164.     split(t0, t0l, t0r, x);
  165.     split(t1, t1l, t1r, x);
  166.     int rt0l = -1, rt1l = -1;
  167.     {
  168.         Node *cur = t0l;
  169.         while (cur)
  170.         {
  171.             rt0l = cur->x;
  172.             cur = cur->r;
  173.         }
  174.     }
  175.     {
  176.         Node *cur = t1l;
  177.         while (cur)
  178.         {
  179.             rt1l = cur->x;
  180.             cur = cur->r;
  181.         }
  182.     }
  183.     if (rt0l <= rt1l)
  184.     {
  185.         merge(t0l, t0l, cur);
  186.     }
  187.     else
  188.     {
  189.         merge(t1l, t1l, cur);
  190.     }
  191.     merge(t0, t0l, t1r);
  192.     merge(t1, t1l, t0r);
  193. }
  194.  
  195. void erase(Node *&t0, Node *&t1, int x)
  196. {
  197.     Node *t0l = nullptr, *t0r = nullptr, *t1l = nullptr, *t1r = nullptr;
  198.     split(t0, t0l, t0r, x + 1);
  199.     split(t1, t1l, t1r, x + 1);
  200.     Node *buft = nullptr;
  201.     if (checkfind(t0, x))
  202.     {
  203.         split(t0l, t0l, buft, x);
  204.     }
  205.     else
  206.     {
  207.         split(t1l, t1l, buft, x);
  208.     }
  209.     merge(t0, t0l, t1r);
  210.     merge(t1, t1l, t0r);
  211. }
  212.  
  213. int solve()
  214. {
  215.     int n, m;
  216.     scanf("%d %d", &n, &m);
  217.     vector<vi> g(n);
  218.     for (int i = 0; i < n - 1; ++i)
  219.     {
  220.         int x, y;
  221.         scanf("%d %d", &x, &y);
  222.         --x, --y;
  223.         g[x].inb(y);
  224.         g[y].inb(x);
  225.     }
  226.     //LCA PART
  227.     //begin
  228.     vector<vi> up(n, vi(18));
  229.     function<void(int, int)> dfsp = [&](int u, int pr)
  230.     {
  231.         up[u][0] = pr;
  232.         for (int to : g[u])
  233.         {
  234.             if (to == pr)
  235.                 continue;
  236.             dfsp(to, u);
  237.         }
  238.     };
  239.     dfsp(0, 0);
  240.     for (int l = 1; l < 18; ++l)
  241.     {
  242.         for (int i = 0; i < n; ++i)
  243.         {
  244.             up[i][l] = up[up[i][l - 1]][l - 1];
  245.         }
  246.     }
  247.     vi h(n);
  248.     function<void(int)> dfsh = [&](int u)
  249.     {
  250.         for (int to : g[u])
  251.         {
  252.             if (up[u][0] == to)
  253.                 continue;
  254.             h[to] = h[u] + 1;
  255.             dfsh(to);
  256.         }
  257.     };
  258.     dfsh(0);
  259.     function<int(int, int)> getlca = [&](int x, int y)
  260.     {
  261.         if (h[x] < h[y])
  262.             swap(x, y);
  263.         int dl = h[x] - h[y];
  264.         for (int i = 17; i >= 0; --i)
  265.         {
  266.             if (dl & (1 << i))
  267.                 x = up[x][i];
  268.         }
  269.         for (int i = 17; i >= 0; --i)
  270.         {
  271.             if (up[x][i] != up[y][i])
  272.                 x = up[x][i], y = up[y][i];
  273.         }
  274.         if (x == y)
  275.             return x;
  276.         return up[x][0];
  277.     };
  278.     //end
  279.     vector<vi> add(n), del(n);
  280.     for (int i = 0; i < m; ++i)
  281.     {
  282.         int x, y, c;
  283.         scanf("%d %d %d", &x, &y, &c);
  284.         --x, --y;
  285.         add[x].inb(c);
  286.         add[y].inb(c);
  287.         int lca = getlca(x, y);
  288.         del[lca].inb(c);
  289.         //printf("%d\n", lca + 1);
  290.     }
  291.     Node *t0 = nullptr, *t1 = nullptr;
  292.     vector<ll> ans(n);
  293.     function<void(Node*, Node*&, Node*&)> mergedd = [&](Node * t, Node *&t0, Node*&t1)
  294.     {
  295.         if (!t)
  296.             return;
  297.         insert(t0, t1, t->x);
  298.         mergedd(t->l, t0, t1);
  299.         mergedd(t->r, t0, t1);
  300.         t->l = nullptr;
  301.         t->r = nullptr;
  302.     };
  303.     function<void(int, int, Node*&, Node*&)> dfsans = [&](int u, int pr, Node *&t0, Node *&t1)
  304.     {
  305.         for (int &x : add[u])
  306.             insert(t0, t1, x);
  307.         for (int to : g[u])
  308.         {
  309.             if (to == pr)
  310.                 continue;
  311.             Node *tc0 = nullptr, *tc1 = nullptr;
  312.             dfsans(to, u, tc0, tc1);
  313.             if (getsz(tc0) + getsz(tc1) > getsz(t0) + getsz(t1))
  314.                 swap(tc0, t0), swap(tc1, t1);
  315.             mergedd(tc0, t0, t1);
  316.             mergedd(tc1, t0, t1);
  317.         }
  318.         ans[u] = getsum(t0);
  319.         for (int &x : del[u])
  320.             erase(t0, t1, x);
  321.     };
  322.     dfsans(0, 0, t0, t1);
  323.     for (ll x : ans)
  324.         printf("%lld\n", x);
  325.     return 0;
  326. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement