#pragma once
#include"data-structure/link-cut-tree/lazy-reversible-splay-tree.hpp"
#include"data-structure/link-cut-tree/link-cut-tree-base.hpp"/**
* Author: Teetat T.
* Date: 2024-08-02
* Description: Lazy Link Cut Tree.
* Usage: using Lct = LazyLinkCutTree<Action>;
* using Ptr = Lct::Ptr;
* using Node = Lct::Node;
* vector<Ptr> ptr(n);
* for(int i=0;i<n;i++)ptr[i]=new Node(val[i]);
* auto link=[&](int u,int v){
* Lct::link(ptr[u],ptr[v]);
* };
* auto cut=[&](int u,int v){
* Lct::cut(ptr[u],ptr[v]);
* };
* auto update=[&](int u,int v,const Action::Tag &val){
* Lct::apply(ptr[u],ptr[v],val);
* };
* auto query=[&](int u,int v){
* return Lct::fold(ptr[u],ptr[v]);
* };
*/template<classMonoidAction>structLazyLinkCutTree:LinkCutTreeBase<LazyReversibleSplayTree<MonoidAction>>{usingbase=LinkCutTreeBase<LazyReversibleSplayTree<MonoidAction>>;usingPtr=typenamebase::Ptr;usingTag=typenameMonoidAction::Tag;voidapply(Ptru,Ptrv,constTag&val){this->evert(u);this->expose(v);this->propagate(v,val);}};
#line 2 "data-structure/link-cut-tree/splay-tree-base.hpp"
/**
* Author: Teetat T.
* Date: 2024-04-13
* Description: Splay Tree. splay(u) will make node u be the root of the tree in amortized O(log n) time.
*/template<classNode>structSplayTreeBase{usingPtr=Node*;boolis_root(Ptrt){return!(t->p)||(t->p->l!=t&&t->p->r!=t);}// The parent of the root stores the path parant in link cut tree.intsize(Ptrt){returnt?t->size:0;}virtualvoidpush(Ptrt){};virtualvoidpull(Ptrt){};intpos(Ptrt){if(t->p){if(t->p->l==t)return-1;if(t->p->r==t)return1;}return0;}voidrotate(Ptrt){Ptrx=t->p,y=x->p;if(pos(t)==-1){if((x->l=t->r))t->r->p=x;t->r=x,x->p=t;}else{if((x->r=t->l))t->l->p=x;t->l=x,x->p=t;}pull(x),pull(t);if((t->p=y)){if(y->l==x)y->l=t;if(y->r==x)y->r=t;}}voidsplay(Ptrt){if(!t)return;push(t);while(!is_root(t)){Ptrx=t->p;if(is_root(x)){push(x),push(t);rotate(t);}else{Ptry=x->p;push(y),push(x),push(t);if(pos(x)==pos(t))rotate(x),rotate(t);elserotate(t),rotate(t);}}}Ptrget_first(Ptrt){while(t->l)push(t),t=t->l;splay(t);returnt;}Ptrget_last(Ptrt){while(t->r)push(t),t=t->r;splay(t);returnt;}Ptrmerge(Ptrl,Ptrr){splay(l),splay(r);if(!l)returnr;if(!r)returnl;l=get_last(l);l->r=r;r->p=l;pull(l);returnl;}pair<Ptr,Ptr>split(Ptrt,intk){if(!t)return{nullptr,nullptr};if(k==0)return{nullptr,t};if(k==size(t))return{t,nullptr};push(t);if(k<=size(t->l)){autox=split(t->l,k);t->l=x.second;t->p=nullptr;if(x.second)x.second->p=t;pull(t);return{x.first,t};}else{autox=split(t->r,k-size(t->l)-1);t->r=x.first;t->p=nullptr;if(x.first)x.first->p=t;pull(t);return{t,x.second};}}voidinsert(Ptr&t,intk,Ptrv){splay(t);autox=split(t,k);t=merge(merge(x.first,v),x.second);}voiderase(Ptr&t,intk){splay(t);autox=split(t,k);autoy=split(x.second,1);// delete y.first;t=merge(x.first,y.second);}template<classT>Ptrbuild(constvector<T>&v){if(v.empty())returnnullptr;function<Ptr(int,int)>build=[&](intl,intr){if(l==r)returnnewNode(v[l]);intm=(l+r)/2;returnmerge(build(l,m),build(m+1,r));};returnbuild(0,v.size()-1);}};#line 2 "data-structure/link-cut-tree/lazy-reversible-bbst.hpp"
/**
* Author: Teetat Info.
* Date: 2024-04-13
* Description: Lazy Reversible BBST Base.
*/template<classTree,classNode,classMonoidAction>structLazyReversibleBBST:Tree{usingTree::merge;usingTree::split;usingtypenameTree::Ptr;usingInfoMonoid=typenameMonoidAction::InfoMonoid;usingTagMonoid=typenameMonoidAction::TagMonoid;usingInfo=typenameMonoidAction::Info;usingTag=typenameMonoidAction::Tag;LazyReversibleBBST()=default;Infosum(Ptrt){returnt?t->sum:InfoMonoid::unit();}voidpull(Ptrt){if(!t)return;push(t);t->size=1;t->sum=t->val;t->revsum=t->val;if(t->l){t->size+=t->l->size;t->sum=InfoMonoid::op(t->l->sum,t->sum);t->revsum=InfoMonoid::op(t->revsum,t->l->revsum);}if(t->r){t->size+=t->r->size;t->sum=InfoMonoid::op(t->sum,t->r->sum);t->revsum=InfoMonoid::op(t->r->revsum,t->revsum);}}voidpush(Ptrt){if(!t)return;if(t->rev){toggle(t->l);toggle(t->r);t->rev=false;}if(t->lz!=TagMonoid::unit()){propagate(t->l,t->lz);propagate(t->r,t->lz);t->lz=TagMonoid::unit();}}voidtoggle(Ptrt){if(!t)return;swap(t->l,t->r);swap(t->sum,t->revsum);t->rev^=true;}voidpropagate(Ptrt,constTag&v){if(!t)return;t->val=MonoidAction::op(t->val,v);t->sum=MonoidAction::op(t->sum,v);t->revsum=MonoidAction::op(t->revsum,v);t->lz=TagMonoid::op(t->lz,v);}voidapply(Ptr&t,intl,intr,constTag&v){if(l>r)return;autox=split(t,l);autoy=split(x.second,r-l+1);propagate(y.first,v);t=merge(x.first,merge(y.first,y.second));}Infoquery(Ptr&t,intl,intr){if(l>r)returnInfoMonoid::unit();autox=split(t,l);autoy=split(x.second,r-l+1);Infores=sum(y.first);t=merge(x.first,merge(y.first,y.second));returnres;}voidreverse(Ptr&t,intl,intr){if(l>r)return;autox=split(t,l);autoy=split(x.second,r-l+1);toggle(y.first);t=merge(x.first,merge(y.first,y.second));}};#line 4 "data-structure/link-cut-tree/lazy-reversible-splay-tree.hpp"
/**
* Author: Teetat T.
* Date: 2024-04-13
* Description: Lazy Reversible Splay Tree.
*/template<classMonoidAction>structLazyReversibleSplayTreeNode{usingPtr=LazyReversibleSplayTreeNode*;usingInfoMonoid=typenameMonoidAction::InfoMonoid;usingTagMonoid=typenameMonoidAction::TagMonoid;usingInfo=typenameMonoidAction::Info;usingTag=typenameMonoidAction::Tag;usingvalue_type=Info;Ptrl,r,p;Infoval,sum,revsum;Taglz;intsize;boolrev;LazyReversibleSplayTreeNode(constInfo&_val=InfoMonoid::unit(),constTag&_lz=TagMonoid::unit()):l(),r(),p(),val(_val),sum(_val),revsum(_val),lz(_lz),size(1),rev(false){}};template<classMonoidAction>structLazyReversibleSplayTree:LazyReversibleBBST<SplayTreeBase<LazyReversibleSplayTreeNode<MonoidAction>>,LazyReversibleSplayTreeNode<MonoidAction>,MonoidAction>{usingNode=LazyReversibleSplayTreeNode<MonoidAction>;};#line 2 "data-structure/link-cut-tree/link-cut-tree-base.hpp"
/**
* Author: Teetat T.
* Date: 2024-05-19
* Description: Link Cut Tree Base.
* Usage:
* evert(u): make u be the root of the tree.
* link(u,v): attach u to v.
* cut(u,v): remove edge between u and v.
* get_root(u): get the root of the tree containing u.
* lca(u,v): get the lowest common ancestor of u and v.
* fold(u,v): get the value of the path from u to v.
*/template<classSplay>structLinkCutTreeBase:Splay{usingNode=typenameSplay::Node;usingPtr=Node*;usingT=typenameNode::value_type;Ptrexpose(Ptrt){Ptrpc=nullptr;// preferred childfor(Ptrcur=t;cur;cur=cur->p){this->splay(cur);cur->r=pc;this->pull(cur);pc=cur;}this->splay(t);returnpc;}voidevert(Ptrt){// make t be the root of the treeexpose(t);this->toggle(t);this->push(t);}voidlink(Ptru,Ptrv){// attach u to vevert(u);expose(v);u->p=v;}voidcut(Ptru,Ptrv){// cut edge between u and vevert(u);expose(v);assert(u->p==v);v->l=u->p=nullptr;this->pull(v);}Ptrget_root(Ptrt){expose(t);while(t->l)this->push(t),t=t->l;this->splay(t);returnt;}Ptrlca(Ptru,Ptrv){if(get_root(u)!=get_root(v))returnnullptr;expose(u);returnexpose(v);}voidset_val(Ptrt,constT&val){this->evert(t);t->val=val;this->pull(t);}Tget_val(Ptrt){this->evert(t);returnt->val;}Tfold(Ptru,Ptrv){evert(u);expose(v);returnv->sum;}};#line 4 "data-structure/link-cut-tree/lazy-link-cut-tree.hpp"
/**
* Author: Teetat T.
* Date: 2024-08-02
* Description: Lazy Link Cut Tree.
* Usage: using Lct = LazyLinkCutTree<Action>;
* using Ptr = Lct::Ptr;
* using Node = Lct::Node;
* vector<Ptr> ptr(n);
* for(int i=0;i<n;i++)ptr[i]=new Node(val[i]);
* auto link=[&](int u,int v){
* Lct::link(ptr[u],ptr[v]);
* };
* auto cut=[&](int u,int v){
* Lct::cut(ptr[u],ptr[v]);
* };
* auto update=[&](int u,int v,const Action::Tag &val){
* Lct::apply(ptr[u],ptr[v],val);
* };
* auto query=[&](int u,int v){
* return Lct::fold(ptr[u],ptr[v]);
* };
*/template<classMonoidAction>structLazyLinkCutTree:LinkCutTreeBase<LazyReversibleSplayTree<MonoidAction>>{usingbase=LinkCutTreeBase<LazyReversibleSplayTree<MonoidAction>>;usingPtr=typenamebase::Ptr;usingTag=typenameMonoidAction::Tag;voidapply(Ptru,Ptrv,constTag&val){this->evert(u);this->expose(v);this->propagate(v,val);}};