Submit Info #2265

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp beet AC 445 ms 12.92 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.72 MiB
max_random_00 AC 445 ms 12.92 MiB
max_random_01 AC 436 ms 12.92 MiB
max_random_02 AC 444 ms 12.92 MiB
random_00 AC 283 ms 8.55 MiB
random_01 AC 315 ms 9.84 MiB
random_02 AC 176 ms 4.16 MiB
random_03 AC 181 ms 10.36 MiB
random_04 AC 116 ms 1.89 MiB
small_00 AC 2 ms 0.71 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 0 ms 0.67 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum" #include<bits/stdc++.h> using namespace std; #define call_from_test #ifndef call_from_test #include<bits/stdc++.h> using namespace std; #endif //BEGIN CUT HERE struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include<bits/stdc++.h> using namespace std; #endif //BEGIN CUT HERE template<typename Node, size_t LIM> struct LinkCutTreeBase{ static array<Node, LIM> pool; size_t ptr; LinkCutTreeBase():ptr(0){} inline Node* create(){ return &pool[ptr++]; } inline Node* create(Node v){ return &(pool[ptr++]=v); } inline size_t idx(Node *t){ return t-&pool[0]; } Node* operator[](size_t k){ return &(pool[k]); } virtual void toggle(Node *t) = 0; virtual void eval(Node *t) = 0; virtual void pushup(Node *t) = 0; void rotR(Node *t){ Node *x=t->p,*y=x->p; if((x->l=t->r)) t->r->p=x; t->r=x;x->p=t; pushup(x);pushup(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; pushup(y); } } void rotL(Node *t){ Node *x=t->p,*y=x->p; if((x->r=t->l)) t->l->p=x; t->l=x;x->p=t; pushup(x);pushup(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; pushup(y); } } bool is_root(Node *t){ return !t->p||(t->p->l!=t&&t->p->r!=t); } void splay(Node *t){ eval(t); while(!is_root(t)){ Node *q=t->p; if(is_root(q)){ eval(q);eval(t); if(q->l==t) rotR(t); else rotL(t); }else{ auto *r=q->p; eval(r);eval(q);eval(t); if(r->l==q){ if(q->l==t) rotR(q),rotR(t); else rotL(t),rotR(t); }else{ if(q->r==t) rotL(q),rotL(t); else rotR(t),rotL(t); } } } } virtual Node* expose(Node *t){ Node *rp=nullptr; for(Node *c=t;c;c=c->p){ splay(c); c->r=rp; pushup(c); rp=c; } splay(t); return rp; } void link(Node *par,Node *c){ expose(c); expose(par); c->p=par; par->r=c; pushup(par); } void cut(Node *c){ expose(c); Node *par=c->l; c->l=nullptr; pushup(c); par->p=nullptr; } void evert(Node *t){ expose(t); toggle(t); eval(t); } Node *parent(Node *t){ expose(t); t=t->l; while(t&&t->r) t=t->r; if(t) splay(t); return t; } Node *root(Node *t){ expose(t); while(t->l) t=t->l; splay(t); return t; } bool is_connected(Node *a,Node *b){ return root(a)==root(b); } Node *lca(Node *a,Node *b){ expose(a); return expose(b); } }; template<typename Node, size_t LIM> array<Node, LIM> LinkCutTreeBase<Node, LIM>::pool; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #ifndef call_from_test #include<bits/stdc++.h> using namespace std; #define call_from_test #include "base.cpp" #undef call_from_test #endif //BEGIN CUT HERE template<typename Tp,typename Ep> struct NodeBase{ using T = Tp; using E = Ep; NodeBase *l,*r,*p; bool rev; T val,dat; E laz; NodeBase(){} NodeBase(T val,E laz): rev(0),val(val),dat(val),laz(laz){ l=r=p=nullptr;} }; template<typename Np, size_t LIM> struct Path : LinkCutTreeBase<Np, LIM>{ using super = LinkCutTreeBase<Np, LIM>; using Node = Np; using T = typename Node::T; using E = typename Node::E; using F = function<T(T, T)>; using G = function<T(T, E)>; using H = function<E(E, E)>; using S = function<T(T)>; F f; G g; H h; S flip; T ti; E ei; Path(F f,G g,H h,T ti,E ei): super(),f(f),g(g),h(h),ti(ti),ei(ei){ flip=[](T a){return a;}; } Path(F f,G g,H h,S flip,T ti,E ei): super(),f(f),g(g),h(h),flip(flip),ti(ti),ei(ei){} Node* create(T val){ return super::create(Node(val,ei)); } inline void propagate(Node *t,E v){ t->laz=h(t->laz,v); t->val=g(t->val,v); t->dat=g(t->dat,v); } inline void toggle(Node *t){ swap(t->l,t->r); t->dat=flip(t->dat); t->rev^=1; } inline void eval(Node *t){ if(t->laz!=ei){ if(t->l) propagate(t->l,t->laz); if(t->r) propagate(t->r,t->laz); t->laz=ei; } if(t->rev){ if(t->l) toggle(t->l); if(t->r) toggle(t->r); t->rev=false; } } inline void pushup(Node *t){ t->dat=t->val; if(t->l) t->dat=f(t->l->dat,t->dat); if(t->r) t->dat=f(t->dat,t->r->dat); } using super::expose; T query(Node *t){ expose(t); return t->dat; } void update(Node *t,E v){ expose(t); propagate(t,v); eval(t); } }; //END CUT HERE #ifndef call_from_test #define call_from_test #include "../tools/fastio.cpp" #include "../mod/mint.cpp" #include "../linearalgebra/squarematrix.cpp" #undef call_from_test // test edge folding signed YUKI_650(){ using M = Mint<int>; using SM = SquareMatrix<M, 2>; using SM2 = pair<SM, SM>; using Node = NodeBase<SM2, SM2>; constexpr size_t LIM = 1e6; using LCT = Path<Node, LIM>; auto f=[](SM2 x,SM2 y){return SM2(x.first*y.first,y.second*x.second);}; auto g=[](SM2 x,SM2 y){(void)x;return y;}; auto flip=[](SM2 x){swap(x.first,x.second);return x;}; SM ti=SM::mul_identity(); SM ei=SM::mul_identity(); SM2 ti2(ti,ti),ei2(ei,ei); LCT lct(f,g,g,flip,ti2,ei2); int n; cin>>n; vector< vector<int> > G(n); vector<int> X,Y; for(int i=1;i<n;i++){ int a,b; cin>>a>>b; X.emplace_back(a); Y.emplace_back(b); G[a].emplace_back(b); G[b].emplace_back(a); } for(int i=0;i<n*2-1;i++) lct.create(ti2); vector< map<int, int> > rev(n); int idx=n; { using P = pair<int, int>; queue<P> q; q.emplace(0,-1); while(!q.empty()){ int v,p; tie(v,p)=q.front();q.pop(); if(~p){ lct.link(lct[p],lct[idx]); lct.link(lct[idx],lct[v]); rev[p][v]=rev[v][p]=idx++; } for(int u:G[v]) if(u!=p) q.emplace(u,v); } } int q; cin>>q; for(int i=0;i<q;i++){ char c; cin>>c; if(c=='x'){ int v,a,b,c,d; cin>>v>>a>>b>>c>>d; int z=rev[X[v]][Y[v]]; lct.expose(lct[z]); SM sm; sm[0][0]=a;sm[0][1]=b; sm[1][0]=c;sm[1][1]=d; lct[z]->val=SM2(sm,sm); lct.pushup(lct[z]); } if(c=='g'){ int x,y; cin>>x>>y; lct.evert(lct[x]); SM ans=lct.query(lct[y]).first; cout<<ans[0][0]<<" "<<ans[0][1]<<" "; cout<<ans[1][0]<<" "<<ans[1][1]<<"\n"; } } cout<<flush; return 0; } /* verified on 2019/12/27 https://yukicoder.me/problems/no/650 */ // test dynamic tree signed SPOJ_DYNACON1(){ int n,m; cin>>n>>m; using Node = NodeBase<int, int>; constexpr size_t LIM = 1e6; using LCT = Path<Node, LIM>; auto f=[](int a,int b){return a+b;}; LCT lct(f,f,f,0,0); for(int i=0;i<n;i++) lct.create(0); for(int i=0;i<m;i++){ string s; int a,b; cin>>s>>a>>b; a--;b--; if(s=="add"s){ lct.evert(lct[b]); lct.link(lct[a],lct[b]); } if(s=="rem"s){ auto v=lct.lca(lct[a],lct[b])==lct[a]?lct[b]:lct[a]; lct.cut(v); } if(s=="conn"s) cout<<(lct.is_connected(lct[a],lct[b])?"YES\n":"NO\n"); } cout<<flush; return 0; } /* verified on 2019/12/27 https://www.spoj.com/problems/DYNACON1/ */ signed main(){ //YUKI_650(); //SPOJ_DYNACON1(); return 0; } #endif #undef call_from_test signed main(){ int n,q; cin>>n>>q; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; using ll = long long; using Node = NodeBase<ll, ll>; auto f=[&](ll a,ll b){return a+b;}; constexpr size_t LIM = 2e5+100; using LCT = Path<Node, LIM>; LCT lct(f,f,f,0,0); for(int i=0;i<n;i++) lct.create(as[i]); for(int i=1;i<n;i++){ int u,v; cin>>u>>v; lct.evert(lct[v]); lct.link(lct[u],lct[v]); } for(int i=0;i<q;i++){ int t; cin>>t; if(t==0){ int u,v,w,x; cin>>u>>v>>w>>x; lct.evert(lct[u]); lct.cut(lct[v]); lct.evert(lct[x]); lct.link(lct[w],lct[x]); } if(t==1){ int p,x; cin>>p>>x; lct.evert(lct[p]); lct.update(lct[p],x); } if(t==2){ int u,v; cin>>u>>v; lct.evert(lct[u]); cout<<lct.query(lct[v])<<"\n"; } } cout<<flush; return 0; }