Submit Info #26904

Problem Lang User Status Time Memory
Dynamic Tree Subtree Add Subtree Sum cpp (anonymous) AC 765 ms 19.99 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.62 MiB
max_random_00 AC 749 ms 19.93 MiB
max_random_01 AC 751 ms 19.92 MiB
max_random_02 AC 754 ms 19.92 MiB
max_random_03 AC 765 ms 19.92 MiB
max_random_04 AC 751 ms 19.99 MiB
random_00 AC 534 ms 13.05 MiB
random_01 AC 530 ms 15.17 MiB
random_02 AC 354 ms 6.12 MiB
random_03 AC 191 ms 16.11 MiB
random_04 AC 257 ms 2.41 MiB
small_00 AC 3 ms 0.67 MiB
small_01 AC 2 ms 0.62 MiB
small_02 AC 0 ms 0.61 MiB
small_03 AC 2 ms 0.61 MiB
small_04 AC 3 ms 0.74 MiB

#pragma GCC optimize("O2,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,ssse3,sse4,sse4.1") #include<bits/stdc++.h> #define apply fuckstl using namespace std; using ll = int64_t; const int maxn = 1<<20, mod = 998244353; struct node { node *l, *r, *p, *pp; int rev, cnt, size, vsize; ll cancel, val, sum, vsum, lazy, add; node() : l(0), r(0), p(0), pp(0), rev(0), cnt(1), size(1), vsize(0), cancel(0), val(0), sum(0), vsum(0), lazy(0), add(0) {} }; using pnode = node*; void apply(pnode v, ll x) { v->val += x; v->sum += x * v->size; v->vsum += x * v->vsize; v->add += x; v->lazy += x; } void push(pnode v) { if(!v) return; if(v->rev) { swap(v->l, v->r); for(auto i : {v->l, v->r}) if(i) { i->rev ^= v->rev; } v->rev = 0; } if(v->lazy) { for(auto i : {v->l, v->r}) if(i) apply(i, v->lazy); v->lazy = 0; } } void update(pnode v) { if(!v) return; v->size = v->vsize+(v->cnt = 1); v->sum = v->val + v->vsum; for(auto i : {v->l, v->r}) if(i) { v->cnt += i->cnt; v->sum += i->sum; v->size += i->size; } } void update_vsub(pnode x, pnode y, int r) { if(r) apply(y, x->add - y->cancel), y->cancel = 0; else y->cancel = x->add; y->pp = r ? 0 : x; x->vsize += r ? -y->size : y->size; x->vsum += r ? -y->sum : y->sum; } void rotate(pnode v) { auto p = v->p, g = p->p; v->p = g; p->p = v; if(g) (g->l == p ? g->l : g->r) = v; if(p->l == v) { p->l = v->r; if(p->l) p->l->p = p; v->r = p; } else { p->r = v->l; if(p->r) p->r->p = p; v->l = p; } update(p); } void clear(pnode v) { if(v) { clear(v->p); push(v); } } void splay(pnode v) { clear(v); while(v->p) { auto p = v->p, g = p->p; if(g) rotate((g->l == p) == (p->l == v) ? p : v); rotate(v); } update(v); } pnode find_kth(pnode v, int k) { push(v); int c = v->l?v->l->cnt:0; if(v->l && k <= c) return find_kth(v->l, k); k -= c+1; if(v->r && k>0) return find_kth(v->r, k); return splay(v), v; } pnode left(pnode v) { splay(v); return find_kth(v, 0); } pnode right(pnode v) { splay(v); return find_kth(v, 1<<30); } pnode merge(pnode u, pnode v) { splay(u); v = left(v); update_vsub(u, v, 1); u->r = v, v->p = u; update(u); return u; } void cut_r(pnode u) { splay(u); if(!u->r) return; auto t = u->r; u->r = 0, t->p = 0; t = left(t); update_vsub(u, t, 0); update(u); } void expose(pnode v) { cut_r(v); v = left(v); while(v->pp) { cut_r(v->pp); v = left(merge(v->pp, v)); } } void make_root(pnode v) { expose(v), splay(v); v->rev = 1; } int size(pnode v) { expose(v), splay(v); return v->size; } void link(pnode u, pnode v) { expose(u), splay(u), make_root(v); update_vsub(u, v, 0); update(u); } void cut(pnode u, pnode v) { make_root(u), cut_r(u), splay(v); update_vsub(u, v, 1); update(u); } pnode root(pnode v) { return expose(v), left(v); } int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; vector<node> f(n); for(int x, i = 0; i < n; i++) { cin >> x; f[i].val = f[i].sum = x; update(&f[i]); //apply(&f[i], x); } for(int x, y, i = 1; i < n; i++) { cin >> x >> y; link(&f[x], &f[y]); } for(int t, u, v, w, x; m--;) { cin >> t; if(t == 0) { cin >> u >> v >> w >> x; cut(&f[u], &f[v]), link(&f[w], &f[x]); } else if(t^2) { cin >> u >> v >> x; cut(&f[u], &f[v]); apply(&f[u], x); link(&f[u], &f[v]); } else { cin >> u >> v; cut(&f[u], &f[v]); cout << f[u].sum << '\n'; link(&f[u], &f[v]); } } }