Submit Info #8376

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 410 ms 12.08 MiB
max_random_01 AC 398 ms 12.05 MiB
max_random_02 AC 403 ms 12.05 MiB
random_00 AC 257 ms 7.99 MiB
random_01 AC 287 ms 9.30 MiB
random_02 AC 157 ms 3.92 MiB
random_03 AC 168 ms 9.66 MiB
random_04 AC 112 ms 1.78 MiB
small_00 AC 4 ms 0.68 MiB
small_01 AC 0 ms 0.67 MiB
small_02 AC 1 ms 0.68 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> struct LinkCutTree{ struct Node{ Node *par_ptr, *left_ptr, *right_ptr; int idx; bool rev; T sum, val; Node(int idx_=-1): idx(idx_), par_ptr(nullptr), left_ptr(nullptr), right_ptr(nullptr){ rev = false; sum = val = 0; } bool is_root(){ return !par_ptr || (par_ptr->left_ptr != this && par_ptr->right_ptr != this); } void toggle(){ if(!rev) return; if(left_ptr) left_ptr->rev ^= true; if(right_ptr) right_ptr->rev ^= true; swap(left_ptr, right_ptr); rev = false; } void pull(){ sum = val; if(left_ptr) sum += left_ptr->sum; if(right_ptr) sum += right_ptr->sum; } void rotl(){ Node *par = par_ptr, *grand_par = par->par_ptr; if((par->right_ptr = left_ptr)) left_ptr->par_ptr = par; left_ptr = par; par->par_ptr = this; par->pull(); pull(); if((par_ptr = grand_par)){ if(grand_par->left_ptr == par) grand_par->left_ptr = this; if(grand_par->right_ptr == par) grand_par->right_ptr = this; grand_par->pull(); } } void rotr(){ Node *par = par_ptr, *grand_par = par->par_ptr; if((par->left_ptr = right_ptr)) right_ptr->par_ptr = par; right_ptr = par; par->par_ptr = this; par->pull(); pull(); if((par_ptr = grand_par)){ if(grand_par->left_ptr == par) grand_par->left_ptr = this; if(grand_par->right_ptr == par) grand_par->right_ptr = this; grand_par->pull(); } } 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; LinkCutTree(int n_): n(n_){ nodes.resize(n); rep(i, n) nodes[i].idx = i; } void toggle_all(Node *node){ if(node->is_root()){ node->toggle(); return; } toggle_all(node->par_ptr); node->toggle(); } 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) node->rotl(); else node->rotr(); return; } Node *grand_par = par->par_ptr; if(par->left_ptr == node){ if(grand_par->left_ptr == par) par->rotr(), node->rotr(); else node->rotr(), node->rotl(); } else{ if(grand_par->right_ptr == par) par->rotl(), node->rotl(); else node->rotl(), node->rotr(); } } } Node *expose(int i){ Node *child = nullptr; for(Node *par=&nodes[i]; par; par=par->par_ptr){ splay(par->idx); par->right_ptr = child; par->pull(); 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]; nodes[par].pull(); } void cut(int child){ expose(child); Node *par = nodes[child].left_ptr; nodes[child].left_ptr = nullptr; par->par_ptr = nullptr; nodes[child].pull(); } void evert(int i){ expose(i); nodes[i].rev = true; } }; int main(){ int n, q; scanf("%d%d", &n, &q); lint a[n]; rep(i, n) scanf("%lld", &a[i]); LinkCutTree<lint> lct(n); rep(i, n) lct.nodes[i].val = lct.nodes[i].sum = a[i]; rep(i, n-1){ int u, v; scanf("%d%d", &u, &v); lct.evert(v); lct.evert(u); lct.link(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.evert(x); lct.cut(y); lct.evert(w); lct.evert(z); lct.link(z, w); } else if(t == 1){ lct.evert(x); lct.nodes[x].val += y; lct.nodes[x].pull(); } else{ lct.evert(x); lct.expose(y); printf("%lld\n", lct.nodes[y].sum); } } }