Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#define _GLIBCXX_DEBUG
- #define _CRT_SECURE_NO_WARNINGS
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef long double ld;
- #define mk make_pair
- #define inb push_back
- #define X first
- #define Y second
- #define all(v) v.begin(), v.end()
- #define sqr(x) (x) * (x)
- #define TIME 1.0 * clock() / CLOCKS_PER_SEC
- #define y1 AYDARBOG
- //continue break pop_back return
- int solve();
- int main()
- {
- //ios_base::sync_with_stdio(0);
- //cin.tie(0);
- #define TASK "hypercube"
- #ifndef _DEBUG
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- solve();
- #ifdef _DEBUG
- fprintf(stderr, "\nTIME: %.3f\n", TIME);
- #endif
- }
- const int BUFSZ = (int)1e5 + 7;
- char buf[BUFSZ];
- string get_str()
- {
- scanf(" %s", buf);
- return string(buf);
- }
- int rand32()
- {
- return (rand() << 15) ^ rand();
- }
- struct Node
- {
- int x, y, sz;
- ll sum;
- Node *l, *r;
- Node() {};
- Node(int val)
- {
- x = sum = val;
- sz = 1;
- y = rand32();
- l = r = nullptr;
- }
- void print()
- {
- printf("%d %d %lld\n", x, sz, sum);
- }
- };
- int getsz(Node *t)
- {
- if (!t)
- return 0;
- return t->sz;
- }
- ll getsum(Node *t)
- {
- if (!t)
- return 0;
- return t->sum;
- }
- void update(Node *&t)
- {
- if (!t)
- return;
- t->sz = getsz(t->l) + getsz(t->r) + 1;
- t->sum = getsum(t->l) + getsum(t->r) + t->x;
- }
- Node *root = nullptr;
- void split(Node *root, Node *&left, Node *&right, int x)
- {
- if (!root)
- {
- left = right = nullptr;
- return;
- }
- if (root->x < x)
- {
- split(root->r, root->r, right, x);
- left = root;
- }
- else
- {
- split(root->l, left, root->l, x);
- right = root;
- }
- update(left);
- update(right);
- update(root);
- }
- void merge(Node *&t, Node *left, Node *right)
- {
- if (!left || !right)
- {
- t = !right ? left : right;
- return;
- }
- if (left->y > right->y)
- {
- merge(left->r, left->r, right);
- t = left;
- }
- else
- {
- merge(right->l, left, right->l);
- t = right;
- }
- update(left);
- update(right);
- update(t);
- }
- void printdd(Node *cur)
- {
- if (!cur)
- return;
- printdd(cur->l);
- printf("%d ", cur->x);
- printdd(cur->r);
- }
- bool checkfind(Node *&t, int x)
- {
- if (!t)
- return 0;
- if (t->x == x)
- return 1;
- if (t->x > x)
- return checkfind(t->l, x);
- return checkfind(t->r, x);
- }
- void insert(Node *&t0, Node *&t1, int x)
- {
- if (checkfind(t0, x) || checkfind(t1, x))
- return;
- Node *cur = new Node(x);
- Node *t0l, *t0r, *t1l, *t1r;
- split(t0, t0l, t0r, x);
- split(t1, t1l, t1r, x);
- int rt0l = -1, rt1l = -1;
- {
- Node *cur = t0l;
- while (cur)
- {
- rt0l = cur->x;
- cur = cur->r;
- }
- }
- {
- Node *cur = t1l;
- while (cur)
- {
- rt1l = cur->x;
- cur = cur->r;
- }
- }
- if (rt0l <= rt1l)
- {
- merge(t0l, t0l, cur);
- }
- else
- {
- merge(t1l, t1l, cur);
- }
- merge(t0, t0l, t1r);
- merge(t1, t1l, t0r);
- }
- void erase(Node *&t0, Node *&t1, int x)
- {
- Node *t0l = nullptr, *t0r = nullptr, *t1l = nullptr, *t1r = nullptr;
- split(t0, t0l, t0r, x + 1);
- split(t1, t1l, t1r, x + 1);
- Node *buft = nullptr;
- if (checkfind(t0, x))
- {
- split(t0l, t0l, buft, x);
- }
- else
- {
- split(t1l, t1l, buft, x);
- }
- merge(t0, t0l, t1r);
- merge(t1, t1l, t0r);
- }
- int solve()
- {
- int n, m;
- scanf("%d %d", &n, &m);
- vector<vi> g(n);
- for (int i = 0; i < n - 1; ++i)
- {
- int x, y;
- scanf("%d %d", &x, &y);
- --x, --y;
- g[x].inb(y);
- g[y].inb(x);
- }
- //LCA PART
- //begin
- vector<vi> up(n, vi(18));
- function<void(int, int)> dfsp = [&](int u, int pr)
- {
- up[u][0] = pr;
- for (int to : g[u])
- {
- if (to == pr)
- continue;
- dfsp(to, u);
- }
- };
- dfsp(0, 0);
- for (int l = 1; l < 18; ++l)
- {
- for (int i = 0; i < n; ++i)
- {
- up[i][l] = up[up[i][l - 1]][l - 1];
- }
- }
- vi h(n);
- function<void(int)> dfsh = [&](int u)
- {
- for (int to : g[u])
- {
- if (up[u][0] == to)
- continue;
- h[to] = h[u] + 1;
- dfsh(to);
- }
- };
- dfsh(0);
- function<int(int, int)> getlca = [&](int x, int y)
- {
- if (h[x] < h[y])
- swap(x, y);
- int dl = h[x] - h[y];
- for (int i = 17; i >= 0; --i)
- {
- if (dl & (1 << i))
- x = up[x][i];
- }
- for (int i = 17; i >= 0; --i)
- {
- if (up[x][i] != up[y][i])
- x = up[x][i], y = up[y][i];
- }
- if (x == y)
- return x;
- return up[x][0];
- };
- //end
- vector<vi> add(n), del(n);
- for (int i = 0; i < m; ++i)
- {
- int x, y, c;
- scanf("%d %d %d", &x, &y, &c);
- --x, --y;
- add[x].inb(c);
- add[y].inb(c);
- int lca = getlca(x, y);
- del[lca].inb(c);
- //printf("%d\n", lca + 1);
- }
- Node *t0 = nullptr, *t1 = nullptr;
- vector<ll> ans(n);
- function<void(Node*, Node*&, Node*&)> mergedd = [&](Node * t, Node *&t0, Node*&t1)
- {
- if (!t)
- return;
- insert(t0, t1, t->x);
- mergedd(t->l, t0, t1);
- mergedd(t->r, t0, t1);
- t->l = nullptr;
- t->r = nullptr;
- };
- function<void(int, int, Node*&, Node*&)> dfsans = [&](int u, int pr, Node *&t0, Node *&t1)
- {
- for (int &x : add[u])
- insert(t0, t1, x);
- for (int to : g[u])
- {
- if (to == pr)
- continue;
- Node *tc0 = nullptr, *tc1 = nullptr;
- dfsans(to, u, tc0, tc1);
- if (getsz(tc0) + getsz(tc1) > getsz(t0) + getsz(t1))
- swap(tc0, t0), swap(tc1, t1);
- mergedd(tc0, t0, t1);
- mergedd(tc1, t0, t1);
- }
- ans[u] = getsum(t0);
- for (int &x : del[u])
- erase(t0, t1, x);
- };
- dfsans(0, 0, t0, t1);
- for (ll x : ans)
- printf("%lld\n", x);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement