Submit Info #8763

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp (anonymous) AC 481 ms 12.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 476 ms 12.12 MiB
max_random_01 AC 461 ms 12.17 MiB
max_random_02 AC 481 ms 12.17 MiB
random_00 AC 293 ms 8.04 MiB
random_01 AC 321 ms 9.30 MiB
random_02 AC 154 ms 3.92 MiB
random_03 AC 195 ms 9.66 MiB
random_04 AC 102 ms 1.80 MiB
small_00 AC 3 ms 0.68 MiB
small_01 AC 2 ms 0.68 MiB
small_02 AC 2 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 { //make_root(u); access(v); cut(v); 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 switch virtual children //if (pre) v->vsub -= pre->sub; //if (v->ch[1]) v->vsub += v->ch[1]->sub; 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() { if (ch[0]) ch[0]->push(); if (ch[1]) ch[1]->push(); 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 splay() // bring this to top of splay tree { 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(); } }; struct node : splay_tree<node*> { using splay_tree::ch; ll val, sval; node() : splay_tree() { } friend ll get_val(node *u) { return u ? u->sval : 0; } void update() override { splay_tree::update(); sval = val + get_val(ch[0]) + get_val(ch[1]); } void push() override { splay_tree::push(); } }; 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]->val = x, lct[i]->update(); for (int i = 1, u, v; i < n; ++i) { cin >> u >> v; lct.link(lct[u], lct[v]); } for (int op, u, v, w, x; q--; ) { cin >> op; if (op == 0) { cin >> u >> v >> w >> x; lct.cut(lct[u], lct[v]); lct.link(lct[w], lct[x]); } if (op == 1) { cin >> u >> w; auto p = lct[u]; lct.access(p); p->val += w; p->update(); } if (op == 2) { cin >> u >> v; lct.make_root(lct[u]); lct.access(lct[v]); cout << get_val(lct[v]->ch[0]) + lct[v]->val << "\n"; } } return 0; }