Submit Info #7198

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp iefnah06 AC 293 ms 10.55 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
max_random_00 AC 289 ms 10.55 MiB
max_random_01 AC 282 ms 10.54 MiB
max_random_02 AC 293 ms 10.55 MiB
random_00 AC 187 ms 7.05 MiB
random_01 AC 208 ms 8.17 MiB
random_02 AC 104 ms 3.54 MiB
random_03 AC 137 ms 8.38 MiB
random_04 AC 65 ms 1.67 MiB
small_00 AC 2 ms 0.68 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 3 ms 0.68 MiB

#ifndef LOCAL #define NDEBUG #endif #include <bits/stdc++.h> using namespace std; using ll = long long; struct node { static node* null; node* p; node* c[2]; bool flip; ll val; ll sum; bool r() { return !(p && p->c[d()] == this); } int d() { assert(p); return p->c[1] == this; } void do_flip() { flip = !flip; swap(c[0], c[1]); } void propagate() { if (flip) { flip = false; for (int i = 0; i < 2; i++) { c[i]->do_flip(); } } } void propagate_all() { assert(p != null); if (!r()) p->propagate_all(); propagate(); } void update() { sum = c[0]->sum + val + c[1]->sum; } void rot() { assert(p); assert(!p->flip); assert(!flip); int x = d(); node* pa = p; node* ch = c[!x]; if (!pa->r()) pa->p->c[pa->d()] = this; p = pa->p; c[!x] = pa; pa->p = this; pa->c[x] = ch; ch->p = pa; pa->update(); update(); } void splay() { propagate_all(); while (!r()) { if (!p->r()) { if (d() == p->d()) { p->rot(); } else { rot(); } } rot(); } } void expose() { splay(); while (p) { p->splay(); p->c[1] = this; rot(); } c[1] = null; update(); assert(r()); } void make_root() { expose(); do_flip(); } void link(node* n) { make_root(); p = n; } void cut() { expose(); assert(c[0] != null); c[0]->p = NULL; c[0] = null; update(); } }; node* node::null = new node(); const int MAXN = 2.1e5; node n[MAXN]; int main() { ios::sync_with_stdio(0), cin.tie(0); node::null->val = node::null->sum = 0; int N, Q; cin >> N >> Q; for (int i = 0; i < N; i++) { n[i].c[0] = n[i].c[1] = node::null; int x; cin >> x; n[i].val = x; n[i].update(); } for (int i = 0; i < N-1; i++) { int u, v; cin >> u >> v; n[u].link(&n[v]); } while (Q--) { int t; cin >> t; if (t == 0) { int u, v, w, x; cin >> u >> v >> w >> x; n[u].make_root(); n[v].cut(); n[w].link(&n[x]); } else if (t == 1) { int p, x; cin >> p >> x; n[p].splay(); n[p].val += x; n[p].update(); } else if (t == 2) { int u, v; cin >> u >> v; n[u].make_root(); n[v].expose(); cout << n[v].sum << '\n'; } else assert(false); } return 0; }