Submit Info #13691

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 284 ms 10.55 MiB
max_random_01 AC 279 ms 10.55 MiB
max_random_02 AC 287 ms 10.55 MiB
random_00 AC 175 ms 7.05 MiB
random_01 AC 197 ms 8.17 MiB
random_02 AC 105 ms 3.55 MiB
random_03 AC 136 ms 8.42 MiB
random_04 AC 64 ms 1.67 MiB
small_00 AC 2 ms 0.68 MiB
small_01 AC 1 ms 0.68 MiB
small_02 AC 0 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; 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() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> q; for (int i = 0; i < n; i++) { nodes[i].c[0] = nodes[i].c[1] = node::null; int x; cin >> x; nodes[i].val = x; nodes[i].upd(); } for (int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; nodes[a].link(&nodes[b]); } //assert(false); for (int _ = 0; _ < q; _++) { int t; cin >> t; if (t == 0) { int u, v, w, x; cin >> u >> v >> w >> x; nodes[u].make_root(); nodes[v].cut(); nodes[w].link(&nodes[x]); } else if (t == 1) { int p, x; cin >> p >> x; nodes[p].splay(); nodes[p].val += x; nodes[p].upd(); } else if (t == 2) { int u, v; cin >> u >> v; nodes[u].make_root(); nodes[v].expose(); cout << nodes[v].total << '\n'; } else assert(false); } }