Submit Info #6552

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp chocorusk AC 512 ms 15.18 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.67 MiB
max_random_00 AC 506 ms 15.10 MiB
max_random_01 AC 512 ms 15.18 MiB
max_random_02 AC 503 ms 15.17 MiB
random_00 AC 316 ms 10.05 MiB
random_01 AC 337 ms 11.55 MiB
random_02 AC 174 ms 4.73 MiB
random_03 AC 210 ms 12.19 MiB
random_04 AC 111 ms 2.05 MiB
small_00 AC 3 ms 0.68 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 2 ms 0.72 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; template<typename Monoid> struct LinkCutTree{ using F=function<Monoid(Monoid, Monoid)>; struct Node{ Node *l, *r, *p; int sz; bool rev; Monoid val, sum; Node(Monoid val):val(val), sum(val), sz(1), rev(false), l(nullptr), r(nullptr), p(nullptr){} bool is_root(){ return !p || (p->l!=this && p->r!=this); } }; const F f; const Monoid e; LinkCutTree(const F f, const Monoid &e):f(f), e(e){} void toggle(Node *t){ if(!t) return; swap(t->l, t->r); t->rev^=true; } void push(Node *t){ if(!t) return; if(t->rev){ toggle(t->l); toggle(t->r); t->rev=false; } } void update(Node *t){ t->sz=1, t->sum=t->val; if(t->l) t->sz+=t->l->sz, t->sum=f(t->l->sum, t->sum); if(t->r) t->sz+=t->r->sz, t->sum=f(t->sum, t->r->sum); } void rotate(Node *t){ Node *p=t->p, *pp=p->p, *ch; if(p->l==t) ch=t->r; else ch=t->l; if(pp){ if(pp->l==p) pp->l=t; else if(pp->r==p) pp->r=t; } t->p=pp; if(p->l==t) t->r=p; else t->l=p; p->p=t; if(p->l==t) p->l=ch; else p->r=ch; if(ch) ch->p=p; update(p); update(t); } int state(Node *t){ if(t->is_root()) return 0; else if(t->p->l==t) return 1; else return -1; } void splay(Node *t){ push(t); while(state(t)){ if(!state(t->p)){ push(t->p); push(t); rotate(t); }else{ push(t->p->p); push(t->p); push(t); if(state(t->p)==state(t)){ rotate(t->p); rotate(t); }else{ rotate(t); rotate(t); } } } } Node *expose(Node *t){ Node *rp=nullptr; for(Node *now=t; now; now=now->p){ splay(now); now->r=rp; update(now); rp=now; } splay(t); return rp; } void link(Node *c, Node *p){//c:root expose(c); expose(p); p->r=c; c->p=p; update(p); } void cut(Node *c){//c->l != nullptr expose(c); c->l->p=nullptr; c->l=nullptr; update(c); } void evert(Node *t){ expose(t); toggle(t); push(t); } }; int main() { int n, q; scanf("%d %d", &n, &q); LinkCutTree<ll> lct([](ll a, ll b){ return a+b;}, 0); using node=LinkCutTree<ll>::Node; vector<node*> vt(n); for(int i=0; i<n; i++){ ll a; scanf("%lld", &a); vt[i]=new node(a); } for(int i=0; i<n-1; i++){ int u, v; scanf("%d %d", &u, &v); lct.evert(vt[u]); lct.link(vt[u], vt[v]); } while(q--){ int t; scanf("%d", &t); if(t==0){ int u, v, w, x; scanf("%d %d %d %d", &u, &v, &w, &x); lct.evert(vt[u]); lct.cut(vt[v]); lct.evert(vt[w]); lct.link(vt[w], vt[x]); }else if(t==1){ int p; ll x; scanf("%d %lld", &p, &x); lct.expose(vt[p]); vt[p]->val+=x; }else{ int u, v; scanf("%d %d", &u, &v); lct.evert(vt[u]); lct.expose(vt[v]); printf("%lld\n", vt[v]->sum); } } return 0; }