Submit Info #36461

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.63 MiB
max_random_00 AC 940 ms 18.48 MiB
max_random_01 AC 903 ms 18.42 MiB
max_random_02 AC 885 ms 18.48 MiB
max_random_03 AC 903 ms 18.39 MiB
max_random_04 AC 930 ms 18.45 MiB
random_00 AC 618 ms 12.11 MiB
random_01 AC 657 ms 14.05 MiB
random_02 AC 387 ms 5.67 MiB
random_03 AC 238 ms 14.80 MiB
random_04 AC 249 ms 2.33 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 2 ms 0.67 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 3 ms 0.37 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; struct TT { template<int tt, class T> static void con(T *x, int d, T *y) { if(x && d >= 0) x->c[tt][d] = y; if(y) y->p = x; } struct node { node *p = 0, *lt = 0; array<array<node*, 2>, 2> c = {}; int cnt = 1, rev = 0; //data here | TODO: move this to a diff struct int subsize = 1; int64_t X = 0, sum = 0, lazy = 0; 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) {//in case p is root of our chain this node will become a part of light tree c[1] = P->c[1]; P->c[1].fill(0); for(auto &i : c[1]) if(i) i->p = this; } con<tt>(P, d, c[tt][!d]); con<tt>(this, !d, P); P->update(); update();//** p = Q; if(!Q) return; if(Q->lt == P) Q->lt = this; for(auto &i : Q->c) for(auto &j : i) if(j == P) j = this; Q->update();//** }//** - probably can be removed by adding some stuff to splay template<int tt> void clear() { if(dir<tt>() >= 0) p->clear<tt>(); push(); } void wtf() { if(p) p->wtf(); push(); } template<int tt> void splay() { clear<tt>(); while(dir<tt>() >= 0) { if(p->dir<tt>() >= 0) { node *x = dir<tt>() == p->dir<tt>() ? p : this; x->rotate<tt>(); } rotate<tt>(); } } void reverse() { swap(c[0][0], c[0][1]), rev ^= 1; } void apply(int64_t val) { sum += subsize*val; X += val; lazy += val; } void push() { if(rev) { for(auto i : c[0]) if(i) i->reverse(); rev = 0; } if(lazy) { for(auto i : c[0]) if(i) i->apply(lazy); for(auto i : c[1]) if(i) i->apply(lazy); if(lt) lt->apply(lazy); lazy = 0; } } void update() { cnt = 1; subsize = 1; sum = X; for(auto i : c[0]) if(i) { cnt += i->cnt; subsize += i->subsize; sum += i->sum; } for(auto i : c[1]) if(i) { subsize += i->subsize; sum += i->sum; } if(lt) subsize += lt->subsize, sum += lt->sum; } }; void expose(node *u) { u->wtf(); u->splay<0>(), u->splay<1>(); //cout << "start\n"; if(auto z = u->c[0][1]) { z->push(); con<1>(z, 1, u->lt); u->lt = z; //cout << z << endl; z->p = u; u->c[0][1] = 0; z->update(); u->update(); } //if(u->p) cout << u << " v " << u->p->lt << endl; for(node *v = u->p; v; v = v->p) { //cout << v << endl; //cout << v->lt << "<3" << endl; v->splay<0>(), v->splay<1>(); auto f = v->lt; //cout << f->c[1][0] << "<3" << endl; if(auto z = v->c[0][1]) { z->push(); z->c[1] = f->c[1]; f->c[1].fill(0);//exclude? for(auto &i : z->c[1]) if(i) i->p = z; z->update(); if(v->lt) v->lt = z; } else if(!f->c[1][0]) { v->lt = f->c[1][1]; if(v->lt) v->lt->p = v; } else { auto x = f->c[1][0]; v->lt = x; if(v->lt) v->lt->p = v; while(x->push(), x->c[1][1]) x = x->c[1][1]; x->splay<1>(); con<1>(x, 1, f->c[1][1]); x->update(); } f->c[1].fill(0); f->update(); v->c[0][1] = f; v->update(); } u->splay<0>(); } int depth(node *x) { expose(x); return x->c[0][0] ? x->c[0][0]->cnt : 0; } void make_root(node *x) { expose(x), x->reverse(); expose(x);//exclude? } void link(node *x, node *y) { expose(x); make_root(y); con<0>(x, 1, y); x->update(); } void cut(node *x) { expose(x); x->c[0][0]->p = 0; x->c[0][0] = 0; x->update(); } void cut(node *x, node *y) { cut(depth(x) > depth(y) ? x : y); } node *root(node *x) { expose(x); while(x->push(), x->c[0][0]) x = x->c[0][0]; x->splay<0>(); return x; } bool connected(node *x, node *y) { return root(x) == root(y); } int size(node *x) { expose(x); return x->subsize; } vector<node> a; TT(int n) : a(n) {} node *operator[](int x) { return &a[x]; } int operator[](node *x) { return x-&a[0]; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n, m, t, a, b, c, d; cin >> n >> m; TT tt(n); for(int t, i = 0; i < n; i++) { cin >> t, tt[i]->apply(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.cut(tt[a]); tt[a]->apply(c); tt.link(tt[b], tt[a]); } else { cin >> a >> b; tt.make_root(tt[b]); tt.cut(tt[a]); cout << tt[a]->sum << '\n'; tt.link(tt[b], tt[a]); } } }