Submit Info #7353

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp KaedeTakagaki AC 513 ms 15.21 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 2.17 MiB
max_random_00 AC 501 ms 15.15 MiB
max_random_01 AC 504 ms 15.21 MiB
max_random_02 AC 513 ms 15.17 MiB
random_00 AC 330 ms 10.55 MiB
random_01 AC 326 ms 11.91 MiB
random_02 AC 158 ms 5.92 MiB
random_03 AC 218 ms 12.51 MiB
random_04 AC 103 ms 3.51 MiB
small_00 AC 3 ms 2.17 MiB
small_01 AC 3 ms 2.17 MiB
small_02 AC 4 ms 2.17 MiB

//Let's join Kaede Takagaki Fan Club !! #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) #define all(x) x.begin(),x.end() template<class T> void dmp(T a){ rep(i,a.size()) cout << a[i] << " "; cout << endl; } template<class T> bool chmax(T&a, T b){ if(a < b){ a = b; return 1; } return 0; } template<class T> bool chmin(T&a, T b){ if(a > b){ a = b; return 1; } return 0; } template<class T> void g(T &a){ cin >> a; } template<class T> void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 1000000007;//998244353 template<class T> void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } struct dat { ll sum; void rv(){} }; dat mrg(dat a, dat b){ return {a.sum + b.sum}; } struct node{ node *p,*l,*r; int id, rev; dat D, S; node(int i, int c) : l(0), r(0), p(0), id(i), rev(0) { D = S = {c}; } //このノードはsplay木の根? (=今いるパスの最上頂点?) bool is_root(){ return !p || (p->l != this && p->r != this); } }; void push(node *n){ if(n->rev){ swap(n->l, n->r); if(n->l) n->l->rev ^= 1, n->l->D.rv(); if(n->r) n->r->rev ^= 1, n->r->D.rv(); n->rev = 0; } } void update(node *n){ push(n); dat slf = n->S; if(n->l) slf = mrg(n->l->D, slf); if(n->r) slf = mrg(slf, n->r->D); n->D = slf; } //右回転 void rotr(node *n){ node *q = n->p, *g = q->p; if((q->l = n->r)) n->r->p = q; n->r = q; q->p = n; if((n->p = g)){ if(g->l == q) g->l = n; else if(g->r == q) g->r = n; } } //左回転 void rotl(node *n){ node *q = n->p, *g = q->p; if((q->r = n->l)) n->l->p = q; n->l = q; q->p = n; if((n->p = g)){ if(g->l == q) g->l = n; else if(g->r == q) g->r = n; } } //スプレー操作 void splay(node *n){ if(n->is_root()){ update(n); return; } while(!n->is_root()){ node *q = n->p; //自分の親がroot、zig if(q->is_root()){ push(q); push(n); if(q->l == n){ rotr(n); } else{ rotl(n); } update(q); update(n); } else{ node *r = q->p; push(r); push(q); push(n); if(r->l == q){ if(q->l == n){ //zig-zig rotr(q); rotr(n); } else{ //zig-zag rotl(n); rotr(n); } } else{ if(q->r == n){ //zig-zig rotl(q); rotl(n); } else{ //zig-zag rotr(n); rotl(n); } } update(r); update(q); update(n); } } } vector<node*>pool; //本質 //xから根までのパスを形成 node *expose(node *x){ node *last = NULL; for(node *pp = x; pp ;pp = pp->p){ //今いるところをsplay splay(pp); //右にさっきまでの木を繋げる pp->r = last; //覚えておく update(pp); last = pp; } splay(x); return last; } void evert(node *n){ expose(n); n->rev ^= 1; n->D.rv(); } node *find_root(node *n){ if(!n) return (node*)NULL; while(1){ push(n); if(n->r) n = n->r; else return n; } } node *cut(node *n){ expose(n); node *p = n->l; n->l->p = NULL; n->l = NULL; update(n); return find_root(p); } void link(node *c, node *p){ expose(c); expose(p); c->p = p; p->r = c; update(p); } //非連結なら-1 int LCA(node *a,node *b){ if(a->id == b->id) return a->id; expose(a); node *ret = expose(b); if(a->p == (node*)NULL) return -1; else return ret->id; } int n, q; int main(){ scanf("%d%d",&n, &q); pool.resize(200005, new node(0, 0)); rep(i, n){ int a; scanf("%d", &a); pool[i] = new node(i, a); } rep(i, n-1){ int u, v; scanf("%d%d", &u, &v); evert(pool[u]); link(pool[u], pool[v]); } rep(i, q){ int ty; scanf("%d",&ty); if(ty == 0){ int u, v, w, x; scanf("%d%d%d%d", &u, &v, &w, &x); evert(pool[v]); cut(pool[u]); evert(pool[w]); link(pool[w], pool[x]); } else if(ty == 1){ int p, x; scanf("%d%d", &p, &x); evert(pool[p]); pool[p]->S.sum += x; update(pool[p]); } else{ int u, v; scanf("%d%d", &u, &v); evert(pool[u]); expose(pool[v]); printf("%lld\n", pool[v]->D.sum); } } }