Submit Info #28435

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
max_random_00 AC 1071 ms 21.55 MiB
max_random_01 AC 1065 ms 21.44 MiB
max_random_02 AC 1054 ms 21.55 MiB
max_random_03 AC 1047 ms 21.45 MiB
max_random_04 AC 1065 ms 21.49 MiB
random_00 AC 686 ms 14.07 MiB
random_01 AC 741 ms 16.29 MiB
random_02 AC 434 ms 6.55 MiB
random_03 AC 258 ms 17.43 MiB
random_04 AC 283 ms 2.55 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 2 ms 0.72 MiB
small_02 AC 2 ms 0.66 MiB
small_03 AC 1 ms 0.72 MiB
small_04 AC 3 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; #ifdef NeverBeRed #include "debug.h" #else #define debug(...) 9715 #endif typedef long long ll; typedef long double ld; typedef complex<ld> point; #define F first #define S second template<class node> struct link_cut_tree { bool connected(node* u, node* v) { return lca(u, v) != NULL; } int depth(node* u) { access(u); return get_sz(u->ch[0]); } node* get_root(node* u) // get root of LCT component { access(u); while (u->ch[0]) u = u->ch[0], u->push(); return access(u), u; } node* ancestor(node* u, int k) // get k-th parent on path to root { k = depth(u) - k; assert(k >= 0); for (; ; u->push()) { int sz = get_sz(u->ch[0]); if (sz == k) return access(u), u; if (sz < k) k -= sz+1, u = u->ch[1]; else u = u->ch[0]; } assert(0); } node* lca(node* u, node* v) { if (u == v) return u; access(u); access(v); if (!u->p) return NULL; u->splay(); return u->p ?: u; } void link(node* u, node* v) // make u parent of v { assert(!connected(u, v)); make_root(v); access(u); set_link(v, u, 0); v->update(); } void cut(node* u) // cut u from its parent { access(u); u->ch[0]->p = NULL; u->ch[0] = NULL; u->update(); } void cut(node* u, node* v) // if u, v adj in tree { cut(depth(u) > depth(v) ? u : v); } void make_root(node* u) // make u root of LCT component { access(u); u->reverse(); access(u); assert(!u->ch[0] && !u->ch[1]); } void access(node *u) // puts u on the preferred path, splay (right subtree is empty) { for (node* v = u, *pre = NULL; v; v = v->p) { v->splay(); // now update virtual children if (pre) v->update_vsub(pre, false); if (v->ch[1]) v->update_vsub(v->ch[1], true); v->ch[1] = pre; v->update(); pre = v; } u->splay(); assert(!u->ch[1]); } node* operator[](int i) { return &data[i]; } int operator[](node* i) { return i - &data[0]; } vector<node> data; link_cut_tree(int n) : data(n) {} }; template<typename pnode> struct splay_tree { pnode ch[2], p; splay_tree() { ch[0] = ch[1] = p = NULL; } int dir() { if (!p) return -2; // root of LCT component if (p->ch[0] == this) return 0; // left child if (p->ch[1] == this) return 1; // right child return -1; // root of current splay tree } bool is_root() { return dir() < 0; } friend void set_link(pnode u, pnode v, int d) { if (v) v->p = u; if (d >= 0) u->ch[d] = v; } void rotate() // assume p and p->p propagated { assert(!is_root()); int x = dir(); pnode g = p; set_link(g->p, static_cast<pnode>(this), g->dir()); set_link(g, ch[x^1], x); set_link(static_cast<pnode>(this), g, x^1); g->update(); //update(); } void splay() // bring this to top of splay tree { const pnode &self = static_cast<pnode>(this); while (!is_root() && !p->is_root()) { p->p->push(), p->push(), self->push(); dir() == p->dir() ? p->rotate() : self->rotate(); self->rotate(); } if (!is_root()) p->push(), self->push(), self->rotate(); self->push(); self->update(); } }; template<typename pnode, class splay_tree_vchs> struct splay_tree_lct : splay_tree<pnode> { splay_tree_vchs vnode; using splay_tree<pnode>::ch; bool rev; int sz; splay_tree_vchs *root; splay_tree_lct() : splay_tree<pnode>() { root = NULL; rev = 0; sz = 1; } friend int get_sz(pnode u) { return u ? u->sz : 0; } void update() { sz = 1 + get_sz(ch[0]) + get_sz(ch[1]); } void push() { if (rev) { if (ch[0]) ch[0]->reverse(); if (ch[1]) ch[1]->reverse(); rev = 0; } } void rotate() { swap(vnode, this->p->vnode); splay_tree<pnode>::rotate(); } void splay() { auto v = &vnode; bool r = !v->key; splay_tree<pnode>::splay(); if (r && v->key) { if (this->p->root->key == NULL) this->p->root = v; if (v->p) v->p->ch[v->p->ch[1] == &v->key->vnode] = v; if (v->ch[0]) v->ch[0]->p = v; if (v->ch[1]) v->ch[1]->p = v; v->key = static_cast<pnode>(this); } } void reverse() { rev ^= 1; swap(ch[0], ch[1]); } void update_vsub(pnode v, bool add) { auto &u = root; if (add) { v->vnode = splay_tree_vchs(v); if (!u) { u = &v->vnode; return; } u->push(); while (u->ch[1]) u = u->ch[1], u->push(); u->ch[1] = &v->vnode; u->ch[1]->p = u; u = u->ch[1]; u->splay(); } else { auto x = &v->vnode; x->splay(); if (!x->ch[0]) { u = x->ch[1]; } else if (!x->ch[1]) { u = x->ch[0]; } else { u = x->ch[0]; u->p = NULL; u->push(); while (u->ch[1]) u = u->ch[1], u->push(); u->ch[1] = x->ch[1]; x->ch[1]->p = u; u->splay(); } if (u) u->p = NULL; x->key = NULL; } } }; template<typename pnode> struct splay_tree_vchs : splay_tree<splay_tree_vchs<pnode>*> { using splay_tree<splay_tree_vchs<pnode>*>::ch; pnode key; splay_tree_vchs() : key(NULL) {}; splay_tree_vchs(const pnode &key) : splay_tree<splay_tree_vchs<pnode>*>(), key(key) { } void update() { key->update(); } void push() { key->push(); } }; struct node : splay_tree_lct<node*, splay_tree_vchs<node*>> { ll x, sub; int rsz; ll lz; node() : splay_tree_lct() { x = sub = 0; rsz = 1; lz = 0; } void apply(ll i) { x += i; sub += (ll)i * rsz; lz += i; } void update() { splay_tree_lct::update(); sub = x; rsz = 1; for (int i = 0; i < 2; ++i) if (ch[i]) { sub += ch[i]->sub; rsz += ch[i]->rsz; } for (int i = 0; i < 2; ++i) if (vnode.ch[i] && vnode.key) { sub += vnode.ch[i]->key->sub; rsz += vnode.ch[i]->key->rsz; } if (root) { sub += root->key->sub; rsz += root->key->rsz; } } void push() { splay_tree_lct::push(); if (lz) { if (ch[0]) ch[0]->apply(lz); if (ch[1]) ch[1]->apply(lz); if (vnode.ch[0] && vnode.key) vnode.ch[0]->key->apply(lz); if (vnode.ch[1] && vnode.key) vnode.ch[1]->key->apply(lz); if (root) root->key->apply(lz); lz = 0; } } void reverse() { splay_tree_lct::reverse(); } }; int main() { #ifdef TurnRed freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); #endif ios_base::sync_with_stdio(0), cin.tie(0); int n, q; cin >> n >> q; link_cut_tree<node> lct(n); for (int i = 0, x; i < n; ++i) { cin >> x; lct[i]->apply(x); } for (int i = 1, u, v; i < n; ++i) { cin >> u >> v; lct.link(lct[u], lct[v]); } for (int t, u, v, w, x; q--; ) { cin >> t; if (t == 0) { cin >> u >> v >> w >> x; lct.cut(lct[u], lct[v]); lct.link(lct[w], lct[x]); } if (t == 1) { cin >> v >> u >> w; lct.make_root(lct[u]); lct.cut(lct[v]); lct[v]->apply(w); lct.link(lct[u], lct[v]); } if (t == 2) { cin >> v >> u; lct.make_root(lct[u]); lct.cut(lct[v]); cout << lct[v]->sub << "\n"; lct.link(lct[u], lct[v]); } } return 0; }