Submit Info #40120

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

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.61 MiB
max_random_00 AC 1422 ms 30.71 MiB
max_random_01 AC 1417 ms 30.67 MiB
max_random_02 AC 1396 ms 30.67 MiB
max_random_03 AC 1395 ms 30.62 MiB
max_random_04 AC 1425 ms 30.67 MiB
random_00 AC 925 ms 19.87 MiB
random_01 AC 984 ms 23.27 MiB
random_02 AC 599 ms 8.92 MiB
random_03 AC 337 ms 24.99 MiB
random_04 AC 376 ms 3.30 MiB
small_00 AC 3 ms 0.80 MiB
small_01 AC 3 ms 0.63 MiB
small_02 AC 1 ms 0.68 MiB
small_03 AC 2 ms 0.67 MiB
small_04 AC 3 ms 0.67 MiB

#include<bits/stdc++.h> using namespace std; using ll = long long; struct func { ll x, y; func(ll X, ll Y) : x(X), y(Y) {} func operator()(const func &f) { return {x*f.x, x*f.y + y}; } ll operator()(const ll &sm, const ll cnt = 1) { return x*sm + y*cnt; } friend bool operator==(const func &a, const func &b) { return a.x == b.x && a.y == b.y; } friend bool operator!=(const func &a, const func &b) { return !(a == b); } }; const func def = {1, 0}; const ll inf = 1ll<<31; template<class T> void con(T a, T &b, T c) { b = c; if(c) c->p = a; } struct TTree { struct node { node *p, *lt; array<array<node*,2>,2> c; int cnt, sub, rev; 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() { auto g = p; int d = dir<tt>(); p = g->p; if(tt == 0) { c[1] = g->c[1]; g->c[1].fill(0); for(auto &i : c[1]) if(i) i->p = this; } con(g, g->c[tt][d], c[tt][!d]); con(this, c[tt][!d], g); g->update(); if(!p) return; if(p->lt == g) p->lt = this; for(auto &i : p->c) for(auto &j : i) if(j == g) j = this; } template<int tt> void clear() { if(dir<tt>() >= 0) p->clear<tt>(); push(); } template<int tt> void splay() { clear<tt>(); int x, y; while((x = dir<tt>()) >= 0) { if((y = p->dir<tt>()) >= 0) (x == y ? p : this)->rotate<tt>(); rotate<tt>(); } update(); } ll sub_sum, sub_max, sub_min, chain_sum, chain_min, chain_max, val; func sub_lazy, chain_lazy; node() : p(0), lt(0), c{}, cnt(1), sub(1), rev(0), sub_max(-inf), sub_min(inf), sub_lazy(def), chain_max(-inf), chain_min(inf), chain_lazy(def), val(0) {} void reverse() {swap(c[0][1], c[0][0]); rev ^= 1; } void apply_sub(func f) { sub_lazy = f(sub_lazy); sub_sum = f(sub_sum, sub-cnt); sub_max = max(-inf, f(sub_max)); sub_min = min(inf, f(sub_min)); } void apply_chain(func f) { chain_lazy = f(chain_lazy); val = f(val); chain_sum = f(chain_sum, cnt); chain_max = f(chain_max); chain_min = f(chain_min); } void push() { if(rev) { for(auto i : c[0]) if(i) i->reverse(); rev = 0; } if(sub_lazy != def) { for(auto i : c[0]) if(i) i->apply_sub(sub_lazy); for(auto i : c[1]) if(i) i->apply_sub(sub_lazy), i->apply_chain(sub_lazy); if(lt) lt->apply_sub(sub_lazy), lt->apply_chain(sub_lazy); sub_lazy = def; } if(chain_lazy != def) { for(auto i : c[0]) if(i) i->apply_chain(chain_lazy); chain_lazy = def; } } template<int type>//0 for real child, 1 for virtual/parallel void add(node *i) { if(!type) cnt += i->cnt; sub += i->sub; (type?sub_sum:chain_sum) += i->chain_sum; (type?sub_max:chain_max) = max((type?sub_max:chain_max), i->chain_max); (type?sub_min:chain_min) = min((type?sub_min:chain_min), i->chain_min); sub_sum += i->sub_sum; sub_max = max(sub_max, i->sub_max); sub_min = min(sub_min, i->sub_min); } void update() { assert(chain_lazy == def && sub_lazy == def); cnt = sub = 1; chain_sum = chain_max = chain_min = val; sub_sum = 0, sub_min = inf, sub_max = -inf; for(auto i : c[0]) if(i) add<0>(i); if(lt) add<1>(lt); for(auto i : c[1]) if(i) add<1>(i); } }; 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 x = v->lt; x->push(); if(auto z = v->c[0][1]) { z->push(); z->c[1] = x->c[1]; con(v, v->lt, z); for(auto &i : z->c[1]) if(i) i->p = z; z->update(); } else if(!x->c[1][0]) { con(v, v->lt, x->c[1][1]); } else { auto z = x->c[1][0]; con(v, v->lt, z); z->push(); while(z->c[1][1]) z = z->c[1][1]; z->splay<1>(); con(z, z->c[1][1], x->c[1][1]); z->update(); } x->c[1].fill(0); v->c[0][1] = x; x->update(); v->update(); } u->splay<0>(); } void make_root(node *v) { expose(v), v->reverse(); } int depth(node *v) { expose(v); return v->c[0][0] ? v->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); if(!v->c[0][0]) return 0; v = v->c[0][0]; while(v->push(), v->c[0][1]) v = v->c[0][1]; v->splay<0>(); return v; } node *root(node *v) { expose(v); while(v->push(), v->c[0][0]) v = v->c[0][0]; v->splay<0>(); return v; } bool connected(node *u, node *v) { return root(u) == root(v); } template<class R, class F> R fetch_subtree(node *v, F f) { node *P = par(v); if(P) cut(v); R r = f(v); if(P) link(P, v); return r; } template<class F> void fetch_subtree(node *v, F f) { node *P = par(v); if(P) cut(v); f(v); if(P) link(P, v); } template<class R, class F> R fetch_chain(node *x, node *y, F f) { node *RT = root(x); make_root(x), expose(y); R r = f(y); make_root(RT); return r; } template<class F> void fetch_chain(node *x, node *y, F f) { node *RT = root(x); make_root(x), expose(y); f(y); make_root(RT); } vector<node> a; TTree(int n) : a(n) {} int operator[](node *v) { return v - &a[0]; } node *operator[](int v) { return &a[v]; } }; 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]->apply_chain({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.fetch_subtree(tt[a], [&](TTree::node *v) { v->apply_chain({1, c}); v->apply_sub({1, c}); } ); } else { cin >> a >> b; tt.make_root(tt[b]); cout << tt.fetch_subtree<ll>(tt[a], [&](TTree::node *v) { return v->chain_sum + v->sub_sum; }) << '\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 */