Submit Info #4403

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp TKO919 AC 473 ms 15.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.67 MiB
max_random_00 AC 473 ms 15.17 MiB
max_random_01 AC 462 ms 15.17 MiB
max_random_02 AC 457 ms 15.17 MiB
random_00 AC 280 ms 10.05 MiB
random_01 AC 321 ms 11.52 MiB
random_02 AC 161 ms 4.80 MiB
random_03 AC 196 ms 12.18 MiB
random_04 AC 105 ms 2.05 MiB
small_00 AC 3 ms 0.68 MiB
small_01 AC 2 ms 0.71 MiB
small_02 AC 1 ms 0.67 MiB

#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; //template #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(a);i>(b);i--) #define ALL(v) (v).begin(),(v).end() typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12; void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;} template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; } template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; } //template end template<typename T>struct LCT{ struct Node{ Node *lp=nullptr,*rp=nullptr,*par=nullptr; T val,sum; int idx,sz=1; bool rev=0; Node(){} Node(int idx,T val):idx(idx),val(val),sum(val){} void eval(){ if(rev){ if(lp)swap(lp->lp,lp->rp),lp->rev^=1; if(rp)swap(rp->lp,rp->rp),rp->rev^=1; rev=0; } } void update(){ sum=val; sz=1; if(lp){sum+=lp->sum; sz+=lp->sz;} if(rp){sum+=rp->sum; sz+=rp->sz;} } bool is_root(){ return !par||(par->lp!=this&&par->rp!=this); } void rotate(){ Node *pp,*p,*c; p=par,pp=p->par; if(p->lp==this){c=rp; rp=p; p->lp=c;} else{c=lp; lp=p; p->rp=c;} if(pp){ if(pp->lp==p)pp->lp=this; if(pp->rp==p)pp->rp=this; } par=pp; p->par=this; if(c)c->par=p; p->update(); update(); } void splay(){ eval(); while(!is_root()){ Node *q=par; if(q->is_root()){ q->eval(); eval(); if(q->lp==this)rotate(); else rotate(); }else{ Node *r=q->par; r->eval(); q->eval(); eval(); if(r->lp==q){ if(q->lp==this){q->rotate(); rotate();} else{rotate(); rotate();} }else{ if(q->rp==this){q->rotate(); rotate();} else{rotate(); rotate();} } } } } }; LCT(){} Node *make(int idx,T val){return new Node(idx,val);} Node *expose(Node *v){ Node *pre=nullptr; for(Node *cur=v;cur;cur=cur->par){ cur->splay(); cur->rp=pre; cur->update(); pre=cur; } v->splay(); return pre; } void link(Node *c,Node *p){ expose(c); expose(p); c->par=p; p->rp=c; p->update(); } void cut(Node *c){ expose(c); c->lp->par=nullptr; c->lp=nullptr; c->update(); } void evert(Node *v){ expose(v); swap(v->lp,v->rp); v->rev^=1; v->eval(); } }; using V=LCT<ll>::Node*; void debug(vector<V> vs){ rep(i,0,vs.size()){ cerr<<"#"<<i<<" "; cerr<<"lp:"; if(vs[i]->lp)cerr<<vs[i]->lp->idx<<" "; else cerr<<"null "; cerr<<"rp:"; if(vs[i]->rp)cerr<<vs[i]->rp->idx<<" "; else cerr<<"null "; cerr<<"par:"; if(vs[i]->par)cerr<<vs[i]->par->idx<<" "; else cerr<<"null "; cerr<<'\n'; } } int main(){ int n,q; scanf("%d%d",&n,&q); LCT<ll> tree; vector<V> vs(n); rep(i,0,n){ int x; scanf("%d",&x); vs[i]=tree.make(i,x); } rep(i,0,n-1){ int x,y; scanf("%d%d",&x,&y); tree.evert(vs[x]); tree.link(vs[x],vs[y]); } rep(i,0,q){ int t; scanf("%d",&t); if(t==0){ int x,y; scanf("%d%d",&x,&y); tree.evert(vs[x]); tree.cut(vs[y]); scanf("%d%d",&x,&y); tree.evert(vs[x]); tree.link(vs[x],vs[y]); } if(t==1){ int p,x; scanf("%d%d",&p,&x); tree.expose(vs[p]); vs[p]->val+=x; vs[p]->update(); } if(t==2){ int x,y; scanf("%d%d",&x,&y); tree.evert(vs[x]); tree.expose(vs[y]); printf("%lld\n",vs[y]->sum); } } return 0; }