Submit Info #36636

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

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.38 MiB
max_random_00 AC 1874 ms 33.67 MiB
max_random_01 AC 1907 ms 33.73 MiB
max_random_02 AC 2004 ms 33.78 MiB
max_random_03 AC 1892 ms 33.68 MiB
max_random_04 AC 1840 ms 33.70 MiB
random_00 AC 1303 ms 21.82 MiB
random_01 AC 1340 ms 25.53 MiB
random_02 AC 814 ms 9.81 MiB
random_03 AC 430 ms 27.55 MiB
random_04 AC 490 ms 3.55 MiB
small_00 AC 3 ms 0.80 MiB
small_01 AC 3 ms 0.73 MiB
small_02 AC 2 ms 0.67 MiB
small_03 AC 3 ms 0.67 MiB
small_04 AC 5 ms 0.67 MiB

//#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx,avx2,sse,sse2,ssse3") #include<bits/stdc++.h> using ll = long long; using namespace std; const ll inf = 1e15; const array<ll, 2> def = {1, 0}; struct TTree { template<class T> static void con(T a, T &b, T c) { b = c; if(c) c->p = a; } struct node { node *p, *lt; array<array<node*,2>,2> c; int cnt, subsize, rev; //split min/max into 3 parts : me | chain-me | subtree-chain //s_sum, subsize is t_sum, tsize in light trees ll val; ll ch_sum, ch_min, ch_max, s_sum, s_min, s_max, t_min, t_max; array<ll, 2> ch_lazy, s_lazy; node() : p(0), lt(0), c{}, cnt(1), subsize(1), rev(0), val(0), ch_sum(0), ch_min(inf), ch_max(-inf), s_sum(0), s_min(inf), s_max(-inf), t_min(inf), t_max(-inf), ch_lazy(def), s_lazy(def) {} template<int tt> int dir() { if(p) { if(p->c[tt][0] == this) return 0; if(p->c[tt][1] == this) return 1; } return -1; } template<int tt> void rotate() { int d = dir<tt>(); auto P = p, Q = p->p; if(!tt) { c[1] = P->c[1]; P->c[1].fill(0); for(auto &i : c[1]) if(i) i->p = this; } con(P, P->c[tt][d], c[tt][!d]); con(this, c[tt][!d], P); p = Q; P->update(); if(!Q) return; if(p->lt == P) p->lt = this; for(auto &i : p->c) for(auto &j : i) if(j == P) j = this; } template<int tt> void clear() { if(dir<tt>() >= 0) p->clear<tt>(); push(); } template<int tt> void splay() { int A, B; clear<tt>(); while((A = dir<tt>()) >= 0) { if((B = p->dir<tt>()) >= 0) (A == B ? p : this)->rotate<tt>(); rotate<tt>(); } update(); if(p) p->update(); } void reverse() {swap(c[0][0], c[0][1]), rev ^= 1; } void push() { if(rev) { for(auto &i : c[0]) if(i) i->reverse(); rev = 0; } if(ch_lazy != def) { for(auto &i : c[0]) if(i) i->ch_apply(ch_lazy); ch_lazy = def; } if(s_lazy != def) { for(auto &i : c[0]) if(i) i->s_apply(s_lazy); if(lt) lt->s_apply(s_lazy); for(auto &i : c[1]) if(i) i->s_apply(s_lazy); s_lazy = def; } } void update_mm() { t_min = min({val, ch_min, s_min}); t_max = max({val, ch_max, s_max}); for(auto &i : c[1]) if(i) { t_min = min(t_min, i->t_min); t_max = max(t_max, i->t_max); } } void update() { cnt = subsize = 1; ch_sum = s_sum = val, t_min = ch_min = s_min = inf, t_max = ch_max = s_max = -inf; for(auto &i : c[0]) if(i) { cnt += i->cnt; subsize += i->subsize; s_sum += i->s_sum; ch_sum += i->ch_sum; ch_min = min({ch_min, i->ch_min, i->val}); ch_max = max({ch_max, i->ch_max, i->val}); s_min = min(s_min, i->s_min); s_max = max(s_max, i->s_max); } if(lt) { subsize += lt->subsize; s_sum += lt->s_sum; s_min = min(s_min, lt->t_min); s_max = max(s_max, lt->t_max); } for(auto &i : c[1]) if(i) { subsize += i->subsize; s_sum += i->s_sum; } update_mm(); } template<bool sub = 0> void ch_apply(array<ll, 2> F) { if(!sub) ch_lazy = {F[0]*ch_lazy[0], F[0]*ch_lazy[1] + F[1]}; if(!sub) val = F[0]*val + F[1]; ch_min = F[0]*ch_min + F[1]; ch_max = F[0]*ch_max + F[1]; if(F[0] < 0) swap(ch_min, ch_max); ch_sum = F[0]*ch_sum + cnt*F[1]; if(!sub) update_mm(); } void s_apply(array<ll, 2> F) { s_lazy = {F[0]*s_lazy[0], F[0]*s_lazy[1] + F[1]}; val = F[0]*val + F[1]; s_min = F[0]*s_min + F[1]; s_max = F[0]*s_max + F[1]; if(F[0] < 0) swap(s_min, s_max); s_sum = F[0]*s_sum + subsize*F[1]; ch_apply<1>(F); update_mm(); } }; void expose(node *u) { u->splay<0>(), u->splay<1>(); if(auto z = u->c[0][1]) { z->push(); con(z, z->c[1][1], u->lt); con(u, u->lt, z); u->c[0][1] = 0; z->update(); u->update(); } for(node *v = u->p; v; v = v->p) { v->splay<0>(), v->splay<1>(); auto l = v->lt; l->push(); if(auto z = v->c[0][1]) { z->push(); z->c[1] = l->c[1]; for(auto &i : z->c[1]) if(i) i->p = z; z->update(); con(v, v->lt, z); } else if(!l->c[1][0]) { con(v, v->lt, l->c[1][1]); } else { auto z = l->c[1][0]; con(v, v->lt, z); while(z->push(), z->c[1][1]) z = z->c[1][1]; z->splay<1>(); con(z, z->c[1][1], l->c[1][1]); z->update(); } v->c[0][1] = l; l->c[1].fill(0); l->update(); v->update(); } u->splay<0>(); } void make_root(node *u) { expose(u), u->reverse(); } int depth(node *u) { expose(u); return u->c[0][0] ? u->c[0][0]->cnt : 0; } void link(node *u, node *v) { expose(u), make_root(v); con(u, u->c[0][1], v); u->update(); } void cut(node *v) { expose(v); v->c[0][0]->p = 0; v->c[0][0] = 0; v->update(); } void cut(node *u, node *v) { cut(depth(u) > depth(v) ? u : v); } node *par(node *v) { expose(v); auto z = v->c[0][0]; if(!z) return 0; while(z->push(), z->c[0][1]) z = z->c[0][1]; return z->splay<0>(), z; } node *root(node *v) { expose(v); while(v->push(), v->c[0][0]) v = v->c[0][0]; return v->splay<0>(), v; } node *left(node *v) {//first in chain v->splay<0>(); while(v->push(), v->c[0][0]) v = v->c[0][0]; return v->splay<0>(), v; } bool connected(node *u, node *v) { return root(u) == root(v); } vector<node> a; TTree(int n) : a(n) {} int operator[](node *u) { return u-&a[0]; } node *operator[](int u) { return &a[u]; } template<class F> void touch_sub(node *v, F func) { auto p = par(v); if(p) cut(v); func(v); if(p) link(p, v); } template<class F> void touch_path(node *u, node *v, F func) { node *r = root(u); make_root(u); expose(v); func(v); make_root(r); } void update_sub(node *_V, array<ll, 2> upd) { touch_sub(_V, [&](node *v) { v->s_apply(upd); }); } ll min_sub(node *_V) { ll res = inf; touch_sub(_V, [&](node *v) { res = v->t_min; }); return res; } ll max_sub(node *_V) { ll res = -inf; touch_sub(_V, [&](node *v) { res = v->t_max; }); return res; } ll sum_sub(node *_V) { ll res = 0; touch_sub(_V, [&](node *v) { res = v->s_sum; }); return res; } void update_path(node *_U, node *_V, array<ll, 2> upd) { touch_path(_U, _V, [&](node *v) { v->ch_apply(upd); }); } ll min_path(node *_U, node *_V) { ll res = inf; touch_path(_U, _V, [&](node *v) { res = min(v->ch_min, v->val); }); return res; } ll max_path(node *_U, node *_V) { ll res = -inf; touch_path(_U, _V, [&](node *v) { res = max(v->ch_max, v->val); }); return res; } ll sum_path(node *_U, node *_V) { ll res = 0; touch_path(_U, _V, [&](node *v) { res = v->ch_sum; }); return res; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n, m, t, a, b, c, d; cin >> n >> m; TTree tt(n); for(int t, i = 0; i < n; i++) { cin >> t, tt[i]->s_apply({0, t}); } for(int f, t, i = 1; i < n; i++) cin >> f >> t, tt.link(tt[f], tt[t]); while(m--) { cin >> t; if(!t) { cin >> a >> b >> c >> d; tt.cut(tt[a], tt[b]); tt.link(tt[c], tt[d]); } else if(t<2) { cin >> a >> b >> c; tt.make_root(tt[b]); tt.update_sub(tt[a], {1, c}); } else { cin >> a >> b; tt.make_root(tt[b]); cout << tt.sum_sub(tt[a]) << '\n'; } } } /* 0. set weight of all nodes in subtree of x as y 1. set root as x 2. set x to y path all weights as z 3. ask minimum weight in x subtree 4. ask maximum weight in x subtree 5. add y to everything in subtree of x 6. add x to y path all weights add z 7. x to y path min weight 8. x to y path max weight 9. set father of x as y, if y is child of x then skip 10. x to y path sum weight 11. ask sum weight in x subtree */