#pragma once
namespaceDynamicRerootingImpl{template<typenamePoint,Point(*rake)(constPoint&,constPoint&)>structSplayTreeforDashedEdge{structNode{Node*l,*r,*p;Pointkey,sum;explicitNode(constPoint&_key):l(nullptr),r(nullptr),p(nullptr),key(_key),sum(_key){}};SplayTreeforDashedEdge(){}usingNP=Node*;voidrotr(NPt){NPx=t->p,y=x->p;if((x->l=t->r))t->r->p=x;t->r=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}voidrotl(NPt){NPx=t->p,y=x->p;if((x->r=t->l))t->l->p=x;t->l=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}voidupdate(NPt){t->sum=t->key;if(t->l)t->sum=rake(t->sum,t->l->sum);if(t->r)t->sum=rake(t->sum,t->r->sum);}NPget_right(NPt){while(t->r)t=t->r;returnt;}NPalloc(constPoint&v){autot=newNode(v);update(t);returnt;}voidsplay(NPt){while(t->p){NPq=t->p;if(!q->p){if(q->l==t)rotr(t);elserotl(t);}else{NPr=q->p;if(r->l==q){if(q->l==t)rotr(q),rotr(t);elserotl(t),rotr(t);}else{if(q->r==t)rotl(q),rotl(t);elserotr(t),rotl(t);}}}}NPinsert(NPt,constPoint&v){if(nott){t=alloc(v);returnt;}else{NPcur=get_right(t),z=alloc(v);splay(cur);z->p=cur;cur->r=z;update(cur);splay(z);returnz;}}NPerase(NPt){splay(t);NPx=t->l,y=t->r;deletet;if(notx){t=y;if(t)t->p=nullptr;}elseif(noty){t=x;t->p=nullptr;}else{x->p=nullptr;t=get_right(x);splay(t);t->r=y;y->p=t;update(t);}returnt;}};template<typenamePath,typenamePoint,typenameInfo,Path(*vertex)(constInfo&),Path(*compress)(constPath&,constPath&),Point(*rake)(constPoint&,constPoint&),Point(*add_edge)(constPath&),Path(*add_vertex)(constPoint&,constInfo&)>structTopTree{private:structNode{Node*l,*r,*p;Infoinfo;Pathkey,sum,mus;typenameSplayTreeforDashedEdge<Point,rake>::Node*light,*belong;boolrev;boolis_root()const{returnnotpor(p->l!=thisandp->r!=this);}explicitNode(constInfo_info):l(nullptr),r(nullptr),p(nullptr),info(_info),light(nullptr),belong(nullptr),rev(false){}};public:usingNP=Node*;SplayTreeforDashedEdge<Point,rake>splay_tree;private:voidtoggle(NPt){swap(t->l,t->r);swap(t->sum,t->mus);t->rev^=true;}voidrotr(NPt){NPx=t->p,y=x->p;push(x),push(t);if((x->l=t->r))t->r->p=x;t->r=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}voidrotl(NPt){NPx=t->p,y=x->p;push(x),push(t);if((x->r=t->l))t->l->p=x;t->l=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}public:TopTree():splay_tree{}{}voidpush(NPt){if(t->rev){if(t->l)toggle(t->l);if(t->r)toggle(t->r);t->rev=false;}}voidpush_rev(NPt){if(t->rev){if(t->l)toggle(t->l);if(t->r)toggle(t->r);t->rev=false;}}voidupdate(NPt){Pathkey=t->light?add_vertex(t->light->sum,t->info):vertex(t->info);Pathsum=key,mus=key;if(t->l)sum=compress(t->l->sum,sum),mus=compress(mus,t->l->mus);if(t->r)sum=compress(sum,t->r->sum),mus=compress(t->r->mus,mus);t->key=key,t->sum=sum,t->mus=mus;}voidsplay(NPt){push(t);{NProt=t;while(notrot->is_root())rot=rot->p;t->belong=rot->belong;if(t!=rot)rot->belong=nullptr;}while(nott->is_root()){NPq=t->p;if(q->is_root()){push_rev(q),push_rev(t);if(q->l==t)rotr(t);elserotl(t);}else{NPr=q->p;push_rev(r),push_rev(q),push_rev(t);if(r->l==q){if(q->l==t)rotr(q),rotr(t);elserotl(t),rotr(t);}else{if(q->r==t)rotl(q),rotl(t);elserotr(t),rotl(t);}}}}NPexpose(NPt){NPrp=nullptr;for(NPcur=t;cur;cur=cur->p){splay(cur);if(cur->r){cur->light=splay_tree.insert(cur->light,add_edge(cur->r->sum));cur->r->belong=cur->light;}cur->r=rp;if(cur->r){splay_tree.splay(cur->r->belong);push(cur->r);cur->light=splay_tree.erase(cur->r->belong);}update(cur);rp=cur;}splay(t);returnrp;}voidlink(NPchild,NPparent){expose(parent);expose(child);child->p=parent;parent->r=child;update(parent);}voidcut(NPchild){expose(child);NPparent=child->l;child->l=nullptr;parent->p=nullptr;update(child);}voidevert(NPt){expose(t);toggle(t);push(t);}NPalloc(constInfo&info){NPt=newNode(info);update(t);returnt;}boolis_connected(NPu,NPv){expose(u),expose(v);returnu==voru->p;}NPlca(NPu,NPv){if(notis_connected(u,v))returnnullptr;expose(u);returnexpose(v);}voidset_key(NPt,constInfo&v){expose(t);t->info=v;update(t);}// u を根とする sumPathquery(NPu){evert(u);returnu->sum;}// root を根, u を部分木の根とする sumPathquery_subtree(NProot,NPu){evert(root);expose(u);NPl=u->l;u->l=nullptr;update(u);autoret=u->sum;u->l=l;update(u);returnret;}};template<typenamePath,typenamePoint,typenameInfo,Path(*vertex)(constInfo&),Path(*compress)(constPath&,constPath&),Point(*rake)(constPoint&,constPoint&),Point(*Add_edge)(constPath&),Path(*add_vertex)(constPoint&,constInfo&)>structDynamicRerooting{intn;TopTree<Path,Point,Info,vertex,compress,rake,Add_edge,add_vertex>tt;usingNP=typenamedecltype(tt)::NP;vector<NP>vs;DynamicRerooting(int_n,constvector<Info>&info):n(_n),vs(n){for(inti=0;i<n;i++)vs[i]=tt.alloc(info[i]);}// u-v 間に辺を追加voidadd_edge(intu,intv){tt.evert(vs[u]);tt.link(vs[u],vs[v]);}// u-v 間の辺を削除voiddel_edge(intu,intv){tt.evert(vs[u]);tt.cut(vs[v]);}// 頂点 u の情報を取得Infoget_info(intu){returnvs[u]->info;}// 頂点 u の情報を設定voidset_info(intu,constInfo&info){tt.set_key(vs[u],info);}// 頂点 u を根とするクエリPathquery(intu){returntt.query(vs[u]);}// 頂点 root を根, 頂点 u を部分木の根とするクエリPathquery_subtree(introot,intu){returntt.query_subtree(vs[root],vs[u]);}};}// namespace DynamicRerootingImplusingDynamicRerootingImpl::DynamicRerooting;usingDynamicRerootingImpl::TopTree;/*
struct Path {
};
struct Point {
};
struct Info {
};
Path vertex(const Info &i) {
}
Path compress(const Path &p, const Path &c) {
}
Point rake(const Point &a, const Point &b) {
}
Point add_edge(const Path &a) {
}
Path add_vertex(const Point &a, const Info &i) {
}
using DR = DynamicRerooting<Path, Point, Info, vertex, compress, rake, add_edge,
add_vertex>;
*/
#line 2 "tree/dynamic-rerooting.hpp"
namespaceDynamicRerootingImpl{template<typenamePoint,Point(*rake)(constPoint&,constPoint&)>structSplayTreeforDashedEdge{structNode{Node*l,*r,*p;Pointkey,sum;explicitNode(constPoint&_key):l(nullptr),r(nullptr),p(nullptr),key(_key),sum(_key){}};SplayTreeforDashedEdge(){}usingNP=Node*;voidrotr(NPt){NPx=t->p,y=x->p;if((x->l=t->r))t->r->p=x;t->r=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}voidrotl(NPt){NPx=t->p,y=x->p;if((x->r=t->l))t->l->p=x;t->l=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}voidupdate(NPt){t->sum=t->key;if(t->l)t->sum=rake(t->sum,t->l->sum);if(t->r)t->sum=rake(t->sum,t->r->sum);}NPget_right(NPt){while(t->r)t=t->r;returnt;}NPalloc(constPoint&v){autot=newNode(v);update(t);returnt;}voidsplay(NPt){while(t->p){NPq=t->p;if(!q->p){if(q->l==t)rotr(t);elserotl(t);}else{NPr=q->p;if(r->l==q){if(q->l==t)rotr(q),rotr(t);elserotl(t),rotr(t);}else{if(q->r==t)rotl(q),rotl(t);elserotr(t),rotl(t);}}}}NPinsert(NPt,constPoint&v){if(nott){t=alloc(v);returnt;}else{NPcur=get_right(t),z=alloc(v);splay(cur);z->p=cur;cur->r=z;update(cur);splay(z);returnz;}}NPerase(NPt){splay(t);NPx=t->l,y=t->r;deletet;if(notx){t=y;if(t)t->p=nullptr;}elseif(noty){t=x;t->p=nullptr;}else{x->p=nullptr;t=get_right(x);splay(t);t->r=y;y->p=t;update(t);}returnt;}};template<typenamePath,typenamePoint,typenameInfo,Path(*vertex)(constInfo&),Path(*compress)(constPath&,constPath&),Point(*rake)(constPoint&,constPoint&),Point(*add_edge)(constPath&),Path(*add_vertex)(constPoint&,constInfo&)>structTopTree{private:structNode{Node*l,*r,*p;Infoinfo;Pathkey,sum,mus;typenameSplayTreeforDashedEdge<Point,rake>::Node*light,*belong;boolrev;boolis_root()const{returnnotpor(p->l!=thisandp->r!=this);}explicitNode(constInfo_info):l(nullptr),r(nullptr),p(nullptr),info(_info),light(nullptr),belong(nullptr),rev(false){}};public:usingNP=Node*;SplayTreeforDashedEdge<Point,rake>splay_tree;private:voidtoggle(NPt){swap(t->l,t->r);swap(t->sum,t->mus);t->rev^=true;}voidrotr(NPt){NPx=t->p,y=x->p;push(x),push(t);if((x->l=t->r))t->r->p=x;t->r=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}voidrotl(NPt){NPx=t->p,y=x->p;push(x),push(t);if((x->r=t->l))t->l->p=x;t->l=x,x->p=t;update(x),update(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}public:TopTree():splay_tree{}{}voidpush(NPt){if(t->rev){if(t->l)toggle(t->l);if(t->r)toggle(t->r);t->rev=false;}}voidpush_rev(NPt){if(t->rev){if(t->l)toggle(t->l);if(t->r)toggle(t->r);t->rev=false;}}voidupdate(NPt){Pathkey=t->light?add_vertex(t->light->sum,t->info):vertex(t->info);Pathsum=key,mus=key;if(t->l)sum=compress(t->l->sum,sum),mus=compress(mus,t->l->mus);if(t->r)sum=compress(sum,t->r->sum),mus=compress(t->r->mus,mus);t->key=key,t->sum=sum,t->mus=mus;}voidsplay(NPt){push(t);{NProt=t;while(notrot->is_root())rot=rot->p;t->belong=rot->belong;if(t!=rot)rot->belong=nullptr;}while(nott->is_root()){NPq=t->p;if(q->is_root()){push_rev(q),push_rev(t);if(q->l==t)rotr(t);elserotl(t);}else{NPr=q->p;push_rev(r),push_rev(q),push_rev(t);if(r->l==q){if(q->l==t)rotr(q),rotr(t);elserotl(t),rotr(t);}else{if(q->r==t)rotl(q),rotl(t);elserotr(t),rotl(t);}}}}NPexpose(NPt){NPrp=nullptr;for(NPcur=t;cur;cur=cur->p){splay(cur);if(cur->r){cur->light=splay_tree.insert(cur->light,add_edge(cur->r->sum));cur->r->belong=cur->light;}cur->r=rp;if(cur->r){splay_tree.splay(cur->r->belong);push(cur->r);cur->light=splay_tree.erase(cur->r->belong);}update(cur);rp=cur;}splay(t);returnrp;}voidlink(NPchild,NPparent){expose(parent);expose(child);child->p=parent;parent->r=child;update(parent);}voidcut(NPchild){expose(child);NPparent=child->l;child->l=nullptr;parent->p=nullptr;update(child);}voidevert(NPt){expose(t);toggle(t);push(t);}NPalloc(constInfo&info){NPt=newNode(info);update(t);returnt;}boolis_connected(NPu,NPv){expose(u),expose(v);returnu==voru->p;}NPlca(NPu,NPv){if(notis_connected(u,v))returnnullptr;expose(u);returnexpose(v);}voidset_key(NPt,constInfo&v){expose(t);t->info=v;update(t);}// u を根とする sumPathquery(NPu){evert(u);returnu->sum;}// root を根, u を部分木の根とする sumPathquery_subtree(NProot,NPu){evert(root);expose(u);NPl=u->l;u->l=nullptr;update(u);autoret=u->sum;u->l=l;update(u);returnret;}};template<typenamePath,typenamePoint,typenameInfo,Path(*vertex)(constInfo&),Path(*compress)(constPath&,constPath&),Point(*rake)(constPoint&,constPoint&),Point(*Add_edge)(constPath&),Path(*add_vertex)(constPoint&,constInfo&)>structDynamicRerooting{intn;TopTree<Path,Point,Info,vertex,compress,rake,Add_edge,add_vertex>tt;usingNP=typenamedecltype(tt)::NP;vector<NP>vs;DynamicRerooting(int_n,constvector<Info>&info):n(_n),vs(n){for(inti=0;i<n;i++)vs[i]=tt.alloc(info[i]);}// u-v 間に辺を追加voidadd_edge(intu,intv){tt.evert(vs[u]);tt.link(vs[u],vs[v]);}// u-v 間の辺を削除voiddel_edge(intu,intv){tt.evert(vs[u]);tt.cut(vs[v]);}// 頂点 u の情報を取得Infoget_info(intu){returnvs[u]->info;}// 頂点 u の情報を設定voidset_info(intu,constInfo&info){tt.set_key(vs[u],info);}// 頂点 u を根とするクエリPathquery(intu){returntt.query(vs[u]);}// 頂点 root を根, 頂点 u を部分木の根とするクエリPathquery_subtree(introot,intu){returntt.query_subtree(vs[root],vs[u]);}};}// namespace DynamicRerootingImplusingDynamicRerootingImpl::DynamicRerooting;usingDynamicRerootingImpl::TopTree;/*
struct Path {
};
struct Point {
};
struct Info {
};
Path vertex(const Info &i) {
}
Path compress(const Path &p, const Path &c) {
}
Point rake(const Point &a, const Point &b) {
}
Point add_edge(const Path &a) {
}
Path add_vertex(const Point &a, const Info &i) {
}
using DR = DynamicRerooting<Path, Point, Info, vertex, compress, rake, add_edge,
add_vertex>;
*/