Submit Info #13696

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp14 iefnah06 AC 207 ms 10.63 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
max_random_00 AC 207 ms 10.63 MiB
max_random_01 AC 199 ms 10.55 MiB
max_random_02 AC 205 ms 10.55 MiB
random_00 AC 125 ms 7.05 MiB
random_01 AC 144 ms 8.17 MiB
random_02 AC 68 ms 3.55 MiB
random_03 AC 94 ms 8.42 MiB
random_04 AC 40 ms 1.67 MiB
small_00 AC 0 ms 0.68 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 4 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; namespace IO { const int SIZE = 1 << 14; char ibuf[SIZE]; int ii = SIZE; char scan_char() { if (ii == SIZE) { int s = fread(ibuf, 1, SIZE, stdin); fill(ibuf + s, ibuf + SIZE, EOF); ii = 0; } return ibuf[ii++]; } int scan_int() { int r = 0; char c; while ((c = scan_char()) < '0') c = scan_char(); r = c - '0'; while ((c = scan_char()) >= '0') r = 10 * r + (c - '0'); return r; } } // namespace IO using namespace IO; struct node { static node* null; node* p; node* c[2]; bool flip; ll val; ll total; bool r() { return !(p && p->c[d()] == this); } int d() { assert(p); return p->c[1] == this; } void upd() { total = c[0]->total + c[1]->total + val; } 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 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->upd(); upd(); } 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; upd(); assert(r()); } void make_root() { expose(); do_flip(); } void link(node* v) { make_root(); p = v; } void cut() { expose(); c[0]->p = NULL; c[0] = null; upd(); } }; node* node::null = new node(); const int MAXN = 2.1e5; int n, q; node nodes[MAXN]; int main() { n = scan_int(); q = scan_int(); for (int i = 0; i < n; i++) { nodes[i].c[0] = nodes[i].c[1] = node::null; int x = scan_int(); nodes[i].val = x; nodes[i].upd(); } for (int i = 0; i < n-1; i++) { int a = scan_int(); int b = scan_int(); nodes[a].link(&nodes[b]); } //assert(false); for (int _ = 0; _ < q; _++) { int t = scan_int(); if (t == 0) { int u = scan_int(); int v = scan_int(); int w = scan_int(); int x = scan_int(); nodes[u].make_root(); nodes[v].cut(); nodes[w].link(&nodes[x]); } else if (t == 1) { int p = scan_int(); int x = scan_int(); nodes[p].splay(); nodes[p].val += x; nodes[p].upd(); } else if (t == 2) { int u = scan_int(); int v = scan_int(); nodes[u].make_root(); nodes[v].expose(); printf("%lld\n", nodes[v].total); } else assert(false); } }