link-cut-tree

const int max_N=1e5;//最大的节点数
namespace Link_Cut_Tree{
    #define rep(d) for(int d=0;d<2;++d)
    typedef struct node*star;
    star null,tail,rt[max_N+1];
    struct node{
        int sz;
        bool rev_flag;
        star p,ch[2];
        inline void update(){
            sz=ch[0]->sz+1+ch[1]->sz;
        }
        inline void putdown(){
            if(rev_flag){
                std::swap(ch[0],ch[1]);
                ch[0]->rev_flag^=1,ch[1]->rev_flag^=1;
                rev_flag=0;
            }
        }
        inline int dir(){
            rep(d)if(p->ch[d]==this)return d;
            return -1;
        }
        inline void set_ch(star x,int d){
            if(~d)ch[d]=x;
            if(x!=null)x->p=this;
        }
    }pool[max_N+1];
    inline star init_null(){
        star x=tail++;
        x->sz=x->rev_flag=0;
        x->ch[0]=x->ch[1]=x->p=x;
        return x;
    }
    inline star new_node(){
        star x=tail++;
        x->sz=1,x->rev_flag=0;
        x->ch[0]=x->ch[1]=x->p=null;
        return x;
    }
    inline void rot(star x){
        register int d,d1;
        star y=x->p;
        d=x->dir(),d1=y->dir();
        y->p->set_ch(x,d1);
        y->set_ch(x->ch[d^1],d),y->update();
        x->set_ch(y,d^1);
    }
    void pd(star x){
        if(~x->dir())pd(x->p); x->putdown();
    }
    inline void splay(star x){
        register int d,d1;
        for(pd(x);~(d=x->dir());rot(x))if(~(d1=x->p->dir()))rot((d^d1)?x:x->p);
        x->update();
    }
    inline void access(star x){
        register star y,rch;
        for(y=x,rch=null;y!=null;rch=y,y=y->p)splay(y),y->set_ch(rch,1),y->update();
        splay(x);
    }
    inline void evert(star x){
        access(x),x->rev_flag^=1;
    }

    inline star get_path(star x,star y){//返回包含x到y的路径上所有点的splay的根
        return evert(x),access(y),y;
    }
    inline void link(star x,star y){//添加一条x到y的边，需要保证添加后仍是树结构
        evert(x),x->p=y;
    }
    inline void cut(star x,star y){//断开x到y之间的边，需要保证这条边存在
        evert(x),access(y);
        x->p=null,y->set_ch(null,0),y->update();
    }

    inline void init(int n){//初始化n个点的森林
        tail=pool,null=init_null();
        for(int i=1;i<=n;++i)rt[i]=new_node();
    }
};

支持链翻转的LCT

namespace Splay{
	typedef struct node*star;
	star null,tail;
	inline star new_node(int val);
	struct node{
		int siz,val,add;
		bool rev;
		star ch[2],p;
		inline int d(){
			if(this==null)return -1;
			rpt(i,0,1)if(p->ch[i]==this)return i;
			return -1;
		}
		inline void set_ch(star x,int d){
			if(this!=null&&~d)ch[d]=x;
			if(x!=null)x->p=this;
		}
		inline void add_it(int a){
			if(this==null)return;
			val+=a,add+=a;
		}
		inline void update(){
			siz=ch[0]->siz+1+ch[1]->siz;
		}
		inline void push_down(){
			if(rev){
				std::swap(ch[0],ch[1]);
				ch[0]->rev^=1,ch[1]->rev^=1;
				rev=0;
			}
			if(add){
				ch[0]->add_it(add),ch[1]->add_it(add);
				add=0;
			}
		}
	}pool[max_N+21];
	inline void rot(star x){
		star y=x->p;
		int d=x->d(),d1=y->d();
		y->p->set_ch(x,d1);
		y->set_ch(x->ch[d^1],d),y->update();
		x->set_ch(y,d^1);
	}
	void pd(star x){
		if(~x->d())pd(x->p);
		x->push_down();
	}
	inline void splay(star x){
		pd(x);
		for(int d,d1;~(d=x->d());rot(x))
			if(~(d1=x->p->d()))rot(d^d1?x:x->p);
		x->update();
	}
	star kth(star x,int k){
		x->push_down();
		int rk=x->ch[0]->siz+1;
		if(rk==k)return x;
		if(rk>k)return kth(x->ch[0],k);
		return kth(x->ch[1],k-rk);
	}
	inline star new_node(int val){
		star x=tail++;
		x->ch[0]=x->ch[1]=x->p=null;
		x->val=val,x->siz=1;
		x->add=x->rev=0;
		return x;
	}
	inline void init(){
		tail=pool;
		null=tail++;
		null->ch[0]=null->ch[1]=null->p=null;
		null->val=null->siz=null->add=null->rev=0;
	}
};
namespace LCT{
	typedef struct node*star;
	star null,tail;
	struct node{
		int siz;
		bool rev;
		star ch[2],p;
		Splay::star link;
		inline int d(){
			if(this==null)return -1;
			rpt(i,0,1)if(p->ch[i]==this)return i;
			return -1;
		}
		inline void set_ch(star x,int d){
			if(this!=null&&~d)ch[d]=x;
			if(x!=null)x->p=this;
		}
		inline void maintain(){
			push_down();
			int rk=ch[0]->siz+1;
			link=Splay::kth(link,rk);
			Splay::splay(link);
		}
		inline void update(){
			siz=ch[0]->siz+1+ch[1]->siz;
		}
		inline void push_down(){
			if(rev){
				std::swap(ch[0],ch[1]);
				ch[0]->rev^=1,ch[1]->rev^=1;
				rev=0;
			}
		}
	}pool[max_N+21];
	inline void rot(star x){
		star y=x->p;
		int d=x->d(),d1=y->d();
		y->p->set_ch(x,d1);
		y->set_ch(x->ch[d^1],d),y->update();
		x->set_ch(y,d^1);
	}
	void pd(star x,star&top){
		if(~x->d())pd(x->p,top);
		else top=x;
		x->push_down();
	}
	inline void splay(star x){
		star top;
		pd(x,top),x->link=top->link;
		for(int d,d1;~(d=x->d());rot(x))
			if(~(d1=x->p->d()))rot(d^d1?x:x->p);
		x->update();
	}
	inline void change_rch(star x,star y){
		x->maintain();
		x->ch[1]->link=x->link->ch[1];
		x->ch[1]->link->p=Splay::null;
		x->set_ch(y,1),x->link->set_ch(y->link,1);
		x->update(),x->link->update();
	}
	inline void Access(star x){
		star rch=null;
		for(star y=x;y!=null;rch=y,y=y->p)splay(y),change_rch(y,rch);
		splay(x);
	}
	inline void Evert(star x){
		Access(x),x->rev^=1,x->link->rev^=1;
	}
	inline star get_path(star x,star y){
		return Evert(x),Access(y),y;
	}
	inline int query(star x){
		Evert(x),Access(x);
		return x->link->val;
	}
	inline star new_node(int val){
		star x=tail++;
		x->ch[0]=x->ch[1]=x->p=null;
		x->siz=1,x->rev=0;
		x->link=Splay::new_node(val);
		return x;
	}
	inline void init(){
		Splay::init();
		tail=pool;
		null=tail++;
		null->ch[0]=null->ch[1]=null->p=null;
		null->link=Splay::null;
		null->siz=null->rev=0;
	}
};