Submit Info #8442

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp Rickypon AC 454 ms 12.05 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
max_random_00 AC 454 ms 12.05 MiB
max_random_01 AC 429 ms 12.05 MiB
max_random_02 AC 446 ms 12.05 MiB
random_00 AC 295 ms 8.03 MiB
random_01 AC 312 ms 9.29 MiB
random_02 AC 162 ms 3.92 MiB
random_03 AC 164 ms 9.61 MiB
random_04 AC 104 ms 1.80 MiB
small_00 AC 2 ms 0.68 MiB
small_01 AC 2 ms 0.68 MiB
small_02 AC 3 ms 0.71 MiB

#include <bits/stdc++.h> #define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i)) #define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i)) #define rep(i, n) For((i), 0, (n)) #define rrep(i, n) rFor((i), (n), 0) #define fi first #define se second #define double long double using namespace std; typedef long long lint; typedef unsigned long long ulint; typedef pair<int, int> pii; typedef pair<lint, lint> pll; template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;} template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;} template<class T> T div_floor(T a, T b){ if(b < 0) a *= -1, b *= -1; return a>=0 ? a/b : (a+1)/b-1; } template<class T> T div_ceil(T a, T b){ if(b < 0) a *= -1, b *= -1; return a>0 ? (a-1)/b+1 : a/b; } constexpr lint mod = 1e9+7; constexpr lint INF = mod * mod; constexpr int MAX = 100010; template<typename T, typename E, typename F, typename G> struct LinkCutTree{ struct Node{ Node *par_ptr, *left_ptr, *right_ptr; int idx; bool rev; T val, sum; Node(): idx(-1), par_ptr(nullptr), left_ptr(nullptr), right_ptr(nullptr), rev(false), val(T{}), sum(T{}){} bool is_root(){ return !par_ptr || (par_ptr->left_ptr != this && par_ptr->right_ptr != this); } void print_data(){ int p = par_ptr ? par_ptr->idx : -1; int l = left_ptr ? left_ptr->idx : -1; int r = right_ptr ? right_ptr->idx : -1; printf("id=%d, p=%d, l=%d, r=%d, rev=%d, val=%lld, sum=%lld\n", idx, p, l ,r, rev, val, sum); } }; int n; vector<Node> nodes; F f; G g; LinkCutTree(int n, T et, F f, G g): n(n), f(f), g(g){ nodes.resize(n); rep(i, n){ nodes[i].idx = i; nodes[i].val = nodes[i].sum = et; } } void toggle(Node *node){ if(!node->rev) return; if(node->left_ptr) node->left_ptr->rev ^= true; if(node->right_ptr) node->right_ptr->rev ^= true; swap(node->left_ptr, node->right_ptr); node->rev = false; } void pull(Node *node){ node->sum = node->val; if(node->left_ptr) node->sum = f(node->left_ptr->sum, node->sum); if(node->right_ptr) node->sum = f(node->sum, node->right_ptr->sum); } void rotl(Node *node){ Node *par = node->par_ptr, *grand_par = par->par_ptr; if((par->right_ptr = node->left_ptr)) node->left_ptr->par_ptr = par; node->left_ptr = par; par->par_ptr = node; pull(par); pull(node); if((node->par_ptr = grand_par)){ if(grand_par->left_ptr == par) grand_par->left_ptr = node; if(grand_par->right_ptr == par) grand_par->right_ptr = node; pull(grand_par); } } void rotr(Node *node){ Node *par = node->par_ptr, *grand_par = par->par_ptr; if((par->left_ptr = node->right_ptr)) node->right_ptr->par_ptr = par; node->right_ptr = par; par->par_ptr = node; pull(par); pull(node); if((node->par_ptr = grand_par)){ if(grand_par->left_ptr == par) grand_par->left_ptr = node; if(grand_par->right_ptr == par) grand_par->right_ptr = node; pull(grand_par); } } void toggle_all(Node *node){ if(node->is_root()){ toggle(node); return; } toggle_all(node->par_ptr); toggle(node); } void splay(int i){ Node *node = &nodes[i]; toggle_all(node); while(!node->is_root()){ Node *par = node->par_ptr; if(par->is_root()){ if(par->right_ptr == node) rotl(node); else rotr(node); return; } Node *grand_par = par->par_ptr; if(par->left_ptr == node){ if(grand_par->left_ptr == par) rotr(par), rotr(node); else rotr(node), rotl(node); } else{ if(grand_par->right_ptr == par) rotl(par), rotl(node); else rotl(node), rotr(node); } } } Node *expose(int i){ Node *child = nullptr; for(Node *par=&nodes[i]; par; par=par->par_ptr){ splay(par->idx); par->right_ptr = child; pull(par); child = par; } splay(i); return child; } void link(int child, int par){ expose(child); expose(par); nodes[child].par_ptr = &nodes[par]; nodes[par].right_ptr = &nodes[child]; pull(&nodes[par]); } void cut(int child){ expose(child); Node *par = nodes[child].left_ptr; nodes[child].left_ptr = nullptr; par->par_ptr = nullptr; pull(&nodes[child]); } void evert(int i){ expose(i); nodes[i].rev = true; toggle(&nodes[i]); } void add_edge(int child, int par){ evert(par); evert(child); link(child, par); } void del_edge(int child, int par){ evert(par); cut(child); } void update_val(int i, E x){ evert(i); nodes[i].val = g(nodes[i].val, x); pull(&nodes[i]); } T get_path_sum(int u, int v){ evert(u); expose(v); return nodes[v].sum; } }; int main(){ int n, q; scanf("%d%d", &n, &q); lint a[n]; rep(i, n) scanf("%lld", &a[i]); LinkCutTree<lint, lint, decltype(plus<>()), decltype(plus<>())> lct(n, 0LL, plus<>(), plus<>()); rep(i, n) lct.update_val(i, a[i]); rep(i, n-1){ int u, v; scanf("%d%d", &u, &v); lct.add_edge(u, v); } rep(_, q){ int t, x, y, z, w; scanf("%d%d%d", &t, &x, &y); if(t == 0){ scanf("%d%d", &z, &w); lct.del_edge(x, y); lct.add_edge(z, w); } else if(t == 1){ lct.update_val(x, y); } else{ printf("%lld\n", lct.get_path_sum(x, y)); } } }