Link-Cut Tree(지식 요약 + 보드 정리)

사고의 근원
https://www.luogu.com.cn/blog/flashblog/solution-p3690
https://www.cnblogs.com/19992147orz/p/8206693.html
https://www.cnblogs.com/candy99/p/6271344.html
선행지식
splay:rotate를 진정으로 이해하고 회구간 뒤집기
나무 사슬 분할: 경중 사슬의 개념
소감
항저우전신 다교 LCT 문제는 120팀에 의해 통과되었는데, 새로운 지식을 배우지 않으면 안 된다. 아이고......
첫 번째 낙곡문제해를 강추했는데 먹을 수 있는 그림이 있어서 좋았는데...
그런데 고구마는 4시간 넘게 배웠어요.
access(x)
현재 루트에 x를 연결하는 경로,
연결한 후 x와 뿌리는 같은 Splay에 있고 x는 깊이가 가장 큰 점입니다.
즉, x에서 뿌리까지의 이 몇 개의 Splay의 직접적인 허변을 실변으로 바꾸고, 원래 대응하는 실변을 허변으로 바꾸었다.
 
구체적인 작업:
먼저 x를 뿌리, Splay(x)로 돌리고,
그리고 x의 오른쪽 트리를 비우고 c[x][1]=0, x와 x보다 깊이가 큰 점의 연결을 강제로 끊는다
x가 오른쪽 트리가 없어서 x라는 노드 유지보수 정보를 업데이트합니다.pushup (x)
 
x가 허변에서 깊이가 더 얕은 Splay로 뛰면 y=f(x)로 뛰면 y로 뛰는 것도 괜찮다
이 과정을 반복해서 Y를 뿌리, Splay(y)로 돌려줍니다.
y의 오른쪽 나무를 비우고 원래의 실변을 허변으로 바꾸면 c[y][1]=0은 y와 y의 원래 오른쪽 나무 간의 연결을 끊는 것을 의미한다.
오른쪽 트리를 이전 작업의 Splay의 뿌리로 설정하고 원래의 빈 모서리를 실제 모서리로 변경합니다. c[y][1]=x는 y라는 Splay와 x라는 Splay를 연결하는 것을 의미합니다.
사실상, 부치문이기 때문에, 공백을 두는 이 조작을 무시할 수 있다
y가 오른쪽 트리로 바뀌었기 때문에 y라는 노드 유지보수 정보를 업데이트합니다.pushup (y)
 
y 깊이가 더 낮은 Splay로 건너뛰고 원래 나무의 뿌리까지 건너뛰기

inline void access(int x){
	for(int y=0;x;y=x,x=f[x])
		splay(x),c[x][1]=y,pushup(x);//    ，        
}

makeroot(x)
뿌리를 바꾸어 x를 원수의 뿌리로 정하고,
실제로 x와 원래의 루트 rt를 연결하는 Splay,access(x)
그리고 이 Splay를 구간 뒤집기 표시로 pushr (x),
r[x] 게으름 표시: 아래로 내려놓을 때 x의 아들 ls,rs의 좌우 나무는 교환되고 그 표시는 뒤집혀야 한다
 
원래 Splay는 심도 증가 순서로 유지되기 때문에
x는 깊이가 가장 큰 점으로 Splay가 뿌리에 닿으면 오른쪽 트리가 없고,
구간을 뒤집는 표시를 한 후 좌우 트리가 서로 바뀌고 x는 결국 왼쪽 트리가 없다.
이것은 x가 이 Splay에서 깊이가 가장 작은 점으로'본말이 뒤바뀌는'역할을 한다는 것을 나타낸다
노드를 바꿔서 나무 전체를 끌어내는 격으로 초롱을 드는 느낌이 든다

inline void pushr(int x){//Splay      
    swap(c[x][0],c[x][1]);
    r[x]^=1;//r          
}
inline void makeroot(int x){
    access(x);splay(x);
    pushr(x);
}

findroot(x)
x가 있는 원목의 뿌리를 찾으면,
주로 x와 y 두 점이 한 나무에 있는지, 즉 연결성을 판단하는 데 쓰인다
먼저 x부터 루트 rt,access(x)로 연결합니다
다시 x를 뿌리, splay(x)로 돌려 복잡도를 확보합니다
끊임없이 왼쪽 트리를 찾고 길 아래에 x의 표시를 놓으면 x의 왼쪽 트리가 뒤집힌 후에
가장 왼쪽 점을 찾을 때까지 깊이가 가장 작은 점입니다. y로 기억하세요.
splay(y) 및 y 값 반환

inline int findroot(R x){
    access(x); splay(x);
    while(c[x][0])pushdown(x),x=c[x][0];
//           ，  pushdown！    update（  findroot pushdown   ）
    splay(x);//     
    return x;
}

split(x,y)
Splay의 실제 체인으로 트리에 있는 경로 (x, y)
트리에 질문(x, y)점 대 사이의 권한과/이 또는 화 따위는 두 개의 체인을 고려해야 한다.
먼저 그 중 하나를 x로 바꿔도 괜찮고, 뿌리로 바꿔도 괜찮습니다.makeroot (x)
Y부터 뿌리까지의 Splay를 뚫어라.access(y), y가 깊이가 가장 큰 점이다
y 를 뿌리, splay (y) 로 돌려라. 이렇게 x와 그 나머지는 y 왼쪽 트리에 있다

inline void split(int x,int y){
    makeroot(x);
    access(y);splay(y);
}

link(x,y)
x-y의 가장자리를 연결하여 나무 위의 x-y 사이에 가장자리가 있는지 주의해서 판단하고,
먼저 x를 루트,makeroot(x)로 지정하고,
x와 y의 연결성을 다시 한번 판정하면findroot(y)==x, 연결이 다시 연결되면 고리가 된다
그렇지 않으면 x와 y가 두 그루의 나무 위에 있다는 것을 설명하고 x라는 나무를 y로 끌어들이면 된다. f[x]=y

inline bool link(int x,int y){
    makeroot(x);
    if(findroot(y)==x)return 0;//          ，      ，          ，      
    f[x]=y;
    return 1;
}

cut(x,y)
x-y가 원래 나무의 가장자리를 끊고 동적 가장자리를 삭제합니다
① 삭제가 합법적임을 보증한다
나무에 있는 경로, split(x, y)를 먼저 꺼내서 split의 조작에 주의하세요.
먼저 makeroot(x), 이때 x는 원래 나무의 뿌리,
다시 access (y), y에서 x로의 경로를 뚫고, Splay에는 y에서 x로의 경로만 있고,
다시 Splay(y), 이때 y는 Splay에서 뿌리,
x는 y와 연결되어 있기 때문에 깊이가 y보다 1이 작고 y의 왼쪽 트리가 틀림없다.
f[x]=0을 직접 명령하면 x의 아버지가 존재하지 않는다는 것을 나타낸다.
c[y][0]=0, y의 왼쪽 트리가 존재하지 않음을 표시하고 y의 정보를 업데이트합니다,pushup(y)

inline void cut(int x,int y){
    split(x,y);
    f[x]=c[y][0]=0;
    pushup(y);//     ，      
}

② 가장자리를 삭제하는 것이 반드시 합법적인 것은 아니다. 즉, 원래 나무의 x-y 사이에 가장자리가 있다는 것을 보장할 수 없다.
 
먼저 x를 루트로 지정,makeroot(x)
(1) y와 x의 연결성을 판단한다. 만약findroot(y)!=x, y와 x가 원수에 연결되지 않고 끝이 없다는 것을 나타낸다(2)
(2)access(y)와 splay(y), splay(x)를 포함하는findroot(y)가 실행되었음을 알 수 있습니다.
현재 x와 y의 경로가 뚫렸습니다. x는 Splay의 루트이고 Splay에는 x에서 y까지의 경로만 있습니다.
만약 y가 Splay에 있는 직통 아버지가 y가 아니라면 f[y]!=x, y와 x 사이에 다른 점이 있다는 것을 설명한다. 그렇지 않으면 돌린다(3)
(3) 이때 f[y]=x는 이미 성립되었지만 y는 x의 오른쪽 트리이고 y는 왼쪽 트리가 있기 때문에 중순으로 xy 사이에 점이 있다.
그래서 만약ch[y][0]!=0, y와 x 사이에 또 다른 점이 있다는 것을 설명한다. 그렇지 않으면 이것은 합법적인 상황임을 설명한다.

inline bool cut(int x,int y){
	makeroot(x);
	if(findroot(y)!=x||f[y]!=x||c[y][0])return 0;
	f[y]=c[x][1]=0;//x findroot(y)      
	pushup(x);
	return 1;
}

합법적인 상황: x, y의 Splay에는 x, y 두 개의 점만 있고 x는 뿌리이며 y는 x의 오른쪽 트리이다
그래서 자수의size 정보를 유지하면 먼저 연결을 판정하고 연결을 판정한 후,
x는 원래 나무 뿌리이고 Splay의 뿌리이며 sz[x]==2이면 합법적이며 그렇지 않으면 합법적이지 않습니다

inline bool cut(int x,int y){
    makeroot(x);
    if(findroot(y)!=x||sz[x]>2)return 0;
    f[y]=c[x][1]=0;
    pushup(x);
    return 1;
}

nroot(x)
not root의 줄임말로 x가 Splay의 루트인지 아닌지를 판단하는 데 사용되며, 1은 Splay의 루트가 아닌 루트를 반환합니다.
f[x]의 의미:
만약 x가 Splay의 뿌리가 아니라면, f[x]=z는 실변이며, x가 Splay에 있는 아버지 z를 대표한다
만약 x가 Splay의 뿌리라면 x가 있는 Splay에서 깊이가 가장 작은 점은 y이고 f[x]=z는 허변으로 y가 원래 나무에 있는 아버지를 대표한다.
ch[x][0/1]의 의미:
동일한 Splay의 점에 사용되는 좌우 아이만 실제 모서리의 반대 모서리라고 볼 수 있습니다.

inline bool nroot(R x){//         Splay  （   Splay   1）
	return c[f[x]][0]==x||c[f[x]][1]==x;
}//     ，       ，           

개인 체험
LCT: Link-cut Tree, 동적 트리
나무가 경중사슬을 나누는 것과 같이 동태나무가 보호하는 것은 하나의 삼림으로 삼림에 허사슬과 실사슬이 있다
각 점은 Splay의 점 번호와 일치하며 총 n개의 점입니다.
각 점 아래에는 하나의 체인만 실체인이고 나머지는 모두 허체인이다
① 점마다 스플레이어에 딱 들어맞는다
② Splay 하나는 깊이 키워드에 따라 실사슬을 유지한다. 즉, 이 Splay를 중순으로 옮겨다니며 깊이 있는 순서에 따라 실사슬에 접근할 수 있다.
허연의 변: 실제로 가리키는 것은 이 Splay에서 번호가 가장 작은 점이 원래 나무에 있는 아버지입니다. 아버지만 아버지로부터 찾을 수 있고 아버지도 자식을 모릅니다.
실사슬의 변: Splay 내부의 변으로 f[]를 통해 아버지를 찾을 수도 있고,ch[][0/1]를 통해 아들을 찾을 수도 있다.
③ Splay의 뿌리와 아버지, 즉 허연변에 대응하는 아버지 때문에
그래서 Splay에서rotate를 생각할 때, xyz를 생각할 때, x의 아버지는 y, y의 아버지는 z,
z는 허연변의 아버지가 될 수 있지만 이런 상황에서 특판이 필요하다. 왜냐하면 이때 z는 회전에 참여하지 않기 때문이다.
이렇게 하면 루트를 바꾸기 전의 루트는 x이고 허체인점은 z이며 f[x]=z이면 루트를 바꾸기 전의 루트는 y이고 반드시 f[y]=z가 있어야 한다.
널빤지 정리
로곡 P3690 동적 나무 템플릿을 예로 들면

#include
#define lc c[x][0]
#define rc c[x][1]
using namespace std;
const int N=3e5+9;
//f:   c:   v:    s:    stk:             r:      
int n,m,f[N],c[N][2],v[N],s[N],stk[N];
bool r[N];
bool nroot(int x){//         Splay  （   Splay   1）
	return c[f[x]][0]==x||c[f[x]][1]==x;
}//     ，       ，           
void pushup(int x){//    
	s[x]=s[lc]^s[rc]^v[x];
}
void pushr(int x){int t=lc;lc=rc;rc=t;r[x]^=1;}//    
void pushdown(int x){//        
	if(r[x]){
		if(lc)pushr(lc);
		if(rc)pushr(rc);
		r[x]=0;
	}
}
void rotate(int x){//    
	int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
	if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;//    if(nroot(y))  ，            （   Splay   2）
	if(w)f[w]=y;f[y]=x;f[x]=z;
	pushup(y);
}
void splay(int x){//       ，            Splay  （   Splay   3）
	int y=x,z=0;
	stk[++z]=y;//st  ，            ，pushdown           （   Splay   4）
	while(nroot(y))stk[++z]=y=f[y];
	while(z)pushdown(stk[z--]);
	while(nroot(x)){
		y=f[x];z=f[y];
		if(nroot(y))
			rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
		rotate(x);
	}
	pushup(x);
}
void access(int x){//  
	for(int y=0;x;x=f[y=x]){
        splay(x),rc=y,pushup(x);
	}
}
void makeroot(int x){//  
	access(x);splay(x);
	pushr(x);
}
int findroot(int x){//  （       ）
	access(x);splay(x);
	while(lc)pushdown(x),x=lc;
	splay(x);
	return x;
}
void split(int x,int y){//    
	makeroot(x);
	access(y);splay(y);
}
void link(int x,int y){//  
	makeroot(x);
	if(findroot(y)!=x)f[x]=y;
}
void cut(int x,int y){//  
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!c[y][0]){
		f[y]=c[x][1]=0;
		pushup(x);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
        scanf("%d",&v[i]);
	}
	while(m--){
	    int type,x,y;
	    scanf("%d%d%d",&type,&x,&y);
		switch(type){
            case 0:split(x,y);printf("%d
",s[y]);break;
            case 1:link(x,y);break;
            case 2:cut(x,y);break;
            case 3:splay(x);v[x]=y;//  x     ，     Splay      ，      ，x       pushup(x)
        }
	}
	return 0;
}