Submit Info #36271

Problem Lang User Status Time Memory
Dynamic Tree Subtree Add Subtree Sum cpp kostia244 AC 513 ms 16.95 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 464 ms 16.90 MiB
max_random_01 AC 490 ms 16.95 MiB
max_random_02 AC 497 ms 16.87 MiB
max_random_03 AC 513 ms 16.90 MiB
max_random_04 AC 493 ms 16.89 MiB
random_00 AC 336 ms 11.11 MiB
random_01 AC 338 ms 12.94 MiB
random_02 AC 204 ms 5.31 MiB
random_03 AC 139 ms 13.50 MiB
random_04 AC 139 ms 2.29 MiB
small_00 AC 3 ms 0.67 MiB
small_01 AC 2 ms 0.70 MiB
small_02 AC 2 ms 0.70 MiB
small_03 AC 1 ms 0.68 MiB
small_04 AC 1 ms 0.67 MiB

#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,ssse3") #include<bits/stdc++.h> #define all(x) begin(x), end(x) using namespace std; using ll=long long; struct link_cut_tree { struct node { node *p; array<node*, 2> c; int cnt, rev, vsize, size; ll x, sum, vsum, add, vadd; node() : p(0), c{0, 0}, cnt(1), rev(0), size(1), vsize(0), x(0), sum(0), vsum(0), add(0), vadd(0) {}; int dir() { if(!p) return -2; if(p->c[0] == this) return 0; if(p->c[1] == this) return 1; return -1; } friend void con(node *x, int d, node *y) { if(x && d >= 0) x->c[d] = y; if(y) y->p = x; } void rotate() { auto op = p; int d = dir(); con(op->p, op->dir(), this); con(op, d, c[!d]); con(this, !d, op); op->update(); } void clear() { if(dir() >= 0) p->clear(); push(); } void splay() { clear(); while(dir() >= 0) { if(p->dir() >= 0) (dir() == p->dir() ? p : this)->rotate(); rotate(); } update(); } void update() { cnt = 1; size = 1+vsize; sum = x+vsum; for(auto i : c) if(i) { cnt += i->cnt; size += i->size; sum += i->sum; } } void reverse() {swap(c[0], c[1]), rev ^= 1;} void apply(ll val) { x += val; sum += size*val; vsum += vsize*val; add += val; vadd += val; } void push() { if(rev) { for(auto i : c) if(i) i->reverse(); rev = 0; } if(add) { for(auto i : c) if(i) i->apply(add); add = 0; } } template<int ad> void update_vsub(node *ch) { if(!ad) ch->apply(vadd); vsize += ad ? ch->size : -ch->size; vsum += ad ? ch->sum : -ch->sum; if(ad) ch->apply(-vadd); } }; void expose(node *u) { for(node *p = 0, *v = u; v; v = v->p) { v->splay(); if(v->c[1]) v->update_vsub<1>(v->c[1]); if(p) v->update_vsub<0>(p); v->c[1] = p, p = v, v->update(); } u->splay(); } int depth(node *v) { expose(v); return v->c[0]?v->c[0]->cnt:0; } void make_root(node *v) { expose(v); v->reverse(); } void link(node *u, node *v) { expose(u), make_root(v); con(u, 1, v);u->update(); } void cut(node *u) { expose(u); u->c[0]->p = 0, u->c[0] = 0; u->update(); } void cut(node *u, node *v) { cut(depth(u) > depth(v) ? u : v); } node *root(node *v) { expose(v); while(v->push(), v->c[0]) v = v->c[0]; return v->splay(), v; } vector<node> a; link_cut_tree(int n) : a(n) {} int operator[](node *x) { return x-&a[0]; } node *operator[](int x) { return &a[x]; } void test() { link(&a[0], &a[1]); make_root(&a[1]); expose(&a[0]); //link(&a[1], &a[2]); //expose(&a[2]); } }; int main() { cin.tie(0)->sync_with_stdio(0); int n, m, t, a, b, c, d; cin >> n >> m; link_cut_tree lct(n); for(int t, i = 0; i < n; i++) { cin >> t, lct[i]->apply(t); } for(int f, t, i = 1; i < n; i++) cin >> f >> t, lct.link(lct[f], lct[t]); while(m--) { cin >> t; if(!t) { cin >> a >> b >> c >> d; lct.cut(lct[a], lct[b]); lct.link(lct[c], lct[d]); } else if(t<2) { cin >> a >> b >> c; lct.make_root(lct[b]); lct.cut(lct[a]); lct[a]->apply(c); lct.link(lct[b], lct[a]); } else { cin >> a >> b; lct.make_root(lct[b]); lct.cut(lct[a]); cout << lct[a]->sum << '\n'; lct.link(lct[b], lct[a]); } } }