Submit Info #47062

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

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.61 MiB
max_random_00 AC 483 ms 18.40 MiB
max_random_01 AC 498 ms 18.40 MiB
max_random_02 AC 518 ms 18.43 MiB
max_random_03 AC 513 ms 18.46 MiB
max_random_04 AC 491 ms 18.48 MiB
random_00 AC 331 ms 12.15 MiB
random_01 AC 343 ms 14.05 MiB
random_02 AC 219 ms 5.68 MiB
random_03 AC 137 ms 14.82 MiB
random_04 AC 157 ms 2.39 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 2 ms 0.68 MiB
small_02 AC 1 ms 0.71 MiB
small_03 AC 1 ms 0.68 MiB
small_04 AC 7 ms 0.71 MiB

#include <bits/stdc++.h> using namespace std; // DEBUG BEGIN #ifdef LOCAL template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){ return out << "(" << p.first << ", " << p.second << ")"; } template<class Tuple, size_t N> struct TuplePrinter{ static ostream &print(ostream &out, const Tuple &t){ return TuplePrinter<Tuple, N-1>::print(out, t) << ", " << get<N-1>(t); } }; template<class Tuple> struct TuplePrinter<Tuple, 1>{ static ostream &print(ostream &out, const Tuple& t){ return out << get<0>(t); } }; template<class... Args> ostream &print_tuple(ostream &out, const tuple<Args...> &t){ return TuplePrinter<decltype(t), sizeof...(Args)>::print(out << "(", t) << ")"; } template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t){ return print_tuple(out, t); } template<class T> ostream &operator<<(class enable_if<!is_same<T, string>::value, ostream>::type &out, const T &arr){ out << "{"; for(auto x: arr) out << x << ", "; return out << (arr.empty() ? "" : "\b\b") << "}"; } template<size_t S> ostream &operator<<(ostream &out, const bitset<S> &b){ for(auto i = 0; i < S; ++ i) out << b[i]; return out; } void debug_out(){ cerr << "\b\b " << endl; } template<class Head, class... Tail> void debug_out(Head H, Tail... T){ cerr << H << ", ", debug_out(T...); } void debug2_out(){ cerr << "\n"; } template<class Head, class... Tail> void debug2_out(Head H, Tail... T){ cerr << "\n"; for(auto x: H) cerr << x << "\n"; debug2_out(T...); } #define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__) #define debug2(...) cerr << "[" << #__VA_ARGS__ << "]", debug2_out(__VA_ARGS__) #else #define debug(...) 42 #define debug2(...) 42 #endif // DEBUG END 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 size(u->ch[0]); } // get root of LCT component node *root(node *u){ access(u); while(u->ch[0]) u = u->ch[0], u->push(); return access(u), u; } // get k-th parent on path to root node *ancestor(node *u, int k){ k = depth(u) - k; assert(k >= 0); for(; ; u->push()){ int sz = size(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; } // make u parent of v void link(node *u, node *v){ assert(!connected(u, v)); make_root(v); access(u); set_link(v, u, 0); v->refresh_auxiliary(); } // cut u from its parent void cut(node *u){ access(u); u->ch[0]->p = NULL; u->ch[0] = NULL; u->refresh_auxiliary(); } // assumes u, v are adjacent in tree void cut(node *u, node *v){ cut(depth(u) > depth(v) ? u : v); } // make u root of LCT component void make_root(node *u){ access(u); u->reverse(); access(u); assert(!u->ch[0] && !u->ch[1]); } // puts u on the preferred path, splay (right subtree is empty) void access(node *u){ for(node *v = u, *pre = NULL; v; v = v->p){ v->splay(); // now refresh virtual children if(pre) v->template refresh_virtual<false>(pre); if(v->ch[1]) v->template refresh_virtual<true>(v->ch[1]); v->ch[1] = pre, v->refresh_auxiliary(), pre = v; } u->splay(); assert(!u->ch[1]); } node *operator[](int i){ return &data[i]; } int operator[](node *u){ return u - &data[0]; } vector<node> data; link_cut_tree(int n): data(n){ } }; template<class ptr> struct splay_tree{ array<ptr, 2> ch = {}; ptr p = {}; bool rev = false; int sz = 1; splay_tree(){ } friend int size(ptr u){ return u ? u->sz : 0; } virtual void refresh_auxiliary(){ sz = 1 + size(ch[0]) + size(ch[1]); } virtual void push(){ if(rev){ if(ch[0]) ch[0]->reverse(); if(ch[1]) ch[1]->reverse(); rev = false; } } virtual void reverse(){ rev ^= true; swap(ch[0], ch[1]); } 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(ptr u, ptr v, int d){ if(v) v->p = u; if(d >= 0) u->ch[d] = v; } // assume p and p->p propagated void rotate(){ assert(!is_root()); int x = dir(); ptr g = p; set_link(g->p, static_cast<ptr>(this), g->dir()); set_link(g, ch[x ^ 1], x); set_link(static_cast<ptr>(this), g, x ^ 1); g->refresh_auxiliary(); //refresh_auxiliary(); } // bring this to top of splay tree void splay(){ 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(), refresh_auxiliary(); } }; // lazy should be I'm ok my childs are not ok (only affect childs) // use reverse when the order of the childs matters (fix the node here) struct node: splay_tree<node *>{ int size = 1; // includes itself, auxiliary subtrees, and virtual subtrees int virtual_size = 0; // includes virtual subtrees long long val = 0; long long subtr_sum = 0; // includes itself, auxiliary subtrees, and virutal subtrees long long virtual_subtr_sum = 0; // includes virtual subtrees long long auxiliary_lazy = 0; long long virtual_lazy = 0; node(){ } // there must be no lazy propagation void refresh_auxiliary() override{ splay_tree::refresh_auxiliary(); assert(auxiliary_lazy == 0); subtr_sum = val + virtual_subtr_sum; size = 1 + virtual_size; for(auto u: ch) if(u){ subtr_sum += u->subtr_sum; size += u->size; } } template<bool add> void refresh_virtual(node *u){ if(!add) u->apply(virtual_lazy); virtual_subtr_sum += (add ? +1 : -1) * u->subtr_sum; virtual_size += (add ? +1 : -1) * u->size; if(add) u->apply(-virtual_lazy); } void push() override{ splay_tree::push(); if(auxiliary_lazy){ for(auto u: ch) if(u) u->apply(auxiliary_lazy); auxiliary_lazy = 0; } } void reverse() override{ splay_tree::reverse(); } void apply(long long lazy){ val += lazy; subtr_sum += lazy * size; virtual_subtr_sum += lazy * virtual_size; auxiliary_lazy += lazy; virtual_lazy += lazy; } }; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n, qn; cin >> n >> qn; link_cut_tree<node> lct(n); for(auto u = 0; u < n; ++ u){ int x; cin >> x; lct[u]->val = lct[u]->subtr_sum = x; } for(auto i = 0; i < n - 1; ++ i){ int u, v; cin >> u >> v; lct.link(lct[u], lct[v]); } for(auto qi = 0; qi < qn; ++ qi){ int type, u; cin >> type >> u; if(type == 0){ int v, w, x; cin >> v >> w >> x; lct.cut(lct[u], lct[v]); lct.link(lct[w], lct[x]); } else if(type == 1){ int p, x; cin >> p >> x; lct.cut(lct[u], lct[p]); lct.make_root(lct[u]); lct[u]->apply(x); lct.link(lct[u], lct[p]); } else{ int p; cin >> p; lct.cut(lct[u], lct[p]); lct.make_root(lct[u]); cout << lct[u]->subtr_sum << "\n"; lct.link(lct[u], lct[p]); } } return 0; } /* */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////