LCT板子

//我坚信LCT可以平替树剖
#include<bits/stdc++.h>
#define ls t[o].ch[0]
#define rs t[o].ch[1]
#define int long long
using namespace std;

const int N=500010;
const int inf=1e9;

int read() {

    int x=0,f=1;
    char ch=getchar();
    while(ch<48||ch>57) {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>=48&&ch<=57) {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;

}

struct LCT {
	int ch[2],fa;
	int val,sum,tag;
	//other_tag,other_values...
}t[N];

bool is_rt(int o) {//判断是否为根节点
	int f=t[o].fa;
	if(t[f].ch[0]!=o&&t[f].ch[1]!=o) return true;
	else return false;
}

void rev(int o) {
	if(!o) return;
	swap(ls,rs);
	t[o].tag^=1;
}

void push_up(int o) {
	//...upd ls rs
	return ;
}

void push_down(int o) {
	//...other_tag
	if(!t[o].tag) return ;
	if(ls) rev(ls);
	if(rs) rev(rs);
	t[o].tag=0;
}

void push(int o) {//翻转整条链
	if(!is_rt(o)) push(t[o].fa);
	push_down(o);
}

void rotate(int o) {//rotate
	int f=t[o].fa;
	int g=t[f].fa;
	int k=t[f].ch[1]==o;
	if(!is_rt(f)) {
		t[g].ch[t[g].ch[1]==f]=o;
	}
	t[o].fa=g;
	t[f].ch[k]=t[o].ch[k^1];
	if(t[o].ch[k^1]) t[t[o].ch[k^1]].fa=f;
	t[f].fa=o;
	t[o].ch[k^1]=f;
	push_up(f);
}

void splay(int o) {//splay

	int f,g;
	push(o);
	while(!is_rt(o)) {
		f=t[o].fa;
		g=t[f].fa;
		if(!is_rt(f)) {
			if((t[g].ch[0]==f)^(t[f].ch[0]==o)) rotate(o);
			else rotate(f);
		}
		rotate(o);
	}
	push_up(o);

}

void access(int o) {//建立从原树根节点到x的一条实链
	for(int i=0;o;i=o,o=t[o].fa) {
		splay(o);
		rs=i;
		push_up(o);
	}
}

void make_rt(int o) {//使x成为原树的根
	access(o);
	splay(o);
	rev(o);//翻转ls与rs，维护中序遍历性质
}

void link(int x,int y) {//x,y之间连一条边
	make_rt(x);
	t[x].fa=y;
}

void split(int x,int y) {//建立从x-y的一条实链
	make_rt(x);
	access(y);
	splay(y);//便利cut操作
}

void cut(int x,int y) {//剪断边(x,y)
	split(x,y);
	if(t[y].ch[0]!=x||t[x].ch[1]) return ;//保证x,y有直接一条边链接
	t[y].ch[0]=t[x].fa=0;
	push_up(x);
}

int LCA(int x,int y) {//lca
	int lca;
	access(x);
	for(int i=0;y;i=y,y=t[y].fa) {
		splay(y);
		t[y].ch[1]=i;
		push_up(y);
		lca=y;
	}
	return lca;
}

int find_rt(int o) {//找到x在原树中的根节点
	access(o);
	splay(o);
	while(ls) {
		push_down(o);
		o=ls;
	}
	return o;
}

signed main() {


    return 0;
}