Submit Info #25766

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

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.67 MiB
max_random_00 AC 533 ms 18.42 MiB
max_random_01 AC 544 ms 18.46 MiB
max_random_02 AC 562 ms 18.49 MiB
max_random_03 AC 552 ms 18.45 MiB
max_random_04 AC 529 ms 18.49 MiB
random_00 AC 362 ms 12.15 MiB
random_01 AC 384 ms 14.05 MiB
random_02 AC 242 ms 5.67 MiB
random_03 AC 160 ms 14.87 MiB
random_04 AC 168 ms 2.36 MiB
small_00 AC 4 ms 0.67 MiB
small_01 AC 1 ms 0.66 MiB
small_02 AC 1 ms 0.68 MiB
small_03 AC 2 ms 0.62 MiB
small_04 AC 3 ms 0.67 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_subtree_add_subtree_sum" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef complex<ll> 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->rev ^= 1; 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; bool rev; int sz; splay_tree() { ch[0] = ch[1] = p = NULL; rev = 0; sz = 1; } friend int get_sz(pnode u) { return u ? u->sz : 0; } virtual void update() { sz = 1 + get_sz(ch[0]) + get_sz(ch[1]); } virtual void push() { if (rev) { if (ch[0]) ch[0]->rev ^= 1; if (ch[1]) ch[1]->rev ^= 1; swap(ch[0], ch[1]); rev = 0; } } 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 _push(pnode p) { if (!p->is_root()) _push(p->p); p->push(); } void _push2(pnode p) { pnode u = NULL; while (!p->is_root()) swap(u, p->p), swap(u, p); swap(u, p->p); while (p) p->push(), swap(u, p->p), swap(u, p); } void splay() // bring this to top of splay tree { _push2(static_cast<pnode>(this)); while (!is_root() && !p->is_root()) { //p->p->push(), p->push(), push(); dir() == p->dir() ? p->rotate() : rotate(); rotate(); } if (!is_root()) /*p->push(), push(),*/ rotate(); //push(); update(); } }; // lazy should be I'm ok my childs are not ok (only affect childs) // calling u->update require no lazy in u struct node : splay_tree<node*> { ll x, sub, vsub; node() : splay_tree() { sub = vsub = 0; } void update() override { splay_tree::update(); sub = x + vsub; sub += (ch[0] ? ch[0]->sub : 0); sub += (ch[1] ? ch[1]->sub : 0); } void update_vsub(node* v, bool add) { vsub += (add ? +1 : -1) * v->sub; } void push() override { splay_tree::push(); } }; struct node_sub_sum : splay_tree<node_sub_sum*> { int rsz, vrsz; ll x, sub, vsub, addsub, addvsub; node_sub_sum() : splay_tree() { x = vrsz = sub = vsub = addsub = addvsub = 0; rsz = 1; } void update() override { splay_tree::update(); assert(addsub == 0); sub = x + vsub; rsz = 1 + vrsz; for (int i = 0; i < 2; ++i) if (ch[i]) sub += ch[i]->sub, rsz += ch[i]->rsz; } void update_vsub(node_sub_sum* v, bool add) { if (!add) v->apply(addvsub); vsub += (add ? +1 : -1) * v->sub; vrsz += (add ? +1 : -1) * v->rsz; if (add) v->apply(-addvsub); } void push() override { splay_tree::push(); if (addsub) { if (ch[0]) ch[0]->apply(addsub); if (ch[1]) ch[1]->apply(addsub); addsub = 0; } } void apply(ll i) { x += i; sub += (ll)i * rsz; vsub += (ll)i * vrsz; addsub += i; addvsub += i; } }; int main() { ios_base::sync_with_stdio(0), cin.tie(0); int n, q; cin >> n >> q; link_cut_tree<node_sub_sum> 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; }