링크-컷 트리

문제

간선이 추가(link)·삭제(cut)되는 동적 포레스트에서, 임의의 두 정점 경로에 대한 질의(합/최대/갱신)와 루트 변경, 연결성 판정을 모두 \(O(\log n)\) amortized에 처리한다. 정적 트리라면 HLD로 충분하지만, 구조 자체가 바뀌면 링크-컷 트리(LCT)가 필요하다.

preferred path 분해

각 정점은 자식들 중 최대 하나를 preferred child 로 지정한다. preferred 간선을 따라가면 트리가 여러 preferred path 로 분해된다. LCT는 각 preferred path를 하나의 스플레이 트리(보조 트리) 로 저장하되, 그 path 위 정점들을 깊이 순(중위 순서) 으로 담는다.

path-parent 포인터

서로 다른 preferred path를 잇기 위해, 한 보조 스플레이 트리의 루트는 path-parent 포인터로 자기 path의 최상단 정점의 실제 트리 부모를 가리킨다. 이 포인터는 스플레이 트리의 일반 부모 포인터와 구분되며, 회전에 영향받지 않는다(preferred child가 아님).

access 연산

LCT의 모든 것은 access(v) 위에 세워진다. access(v) 는 루트에서 \(v\) 까지의 경로를 하나의 preferred path로 만든다. 구현은 \(v\) 를 스플레이로 올린 뒤, path-parent를 따라 위로 올라가며 각 단계에서 preferred child를 교체하고 다시 스플레이한다. access 이후 \(v\) 가 속한 보조 트리가 곧 루트–\(v\) 경로 전체를 담으므로, 그 보조 트리의 집계값(합/최대)이 경로 질의 답이다.

주요 연산

amortized 분석

access의 preferred child 교체 총횟수는 light-edge 논변(heavy-light처럼)으로 한 연산당 amortized \(O(\log n)\) 이고, 스플레이 자체도 amortized \(O(\log n)\). 따라서 전체 \(O(\log n)\) per op. makeRoot의 reverse는 스플레이 트리의 구간 뒤집기 lazy로 처리한다(스플레이 단원과 동일).

핵심 구현 (경로 합 + makeRoot)

스플레이 보조 트리에 rev lazy와 경로 집계 sum 을 둔다.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Node { int ch[2], par, val, sum; bool rev; } t[MAXN];

bool isRoot(int x){ return t[t[x].par].ch[0]!=x && t[t[x].par].ch[1]!=x; }
void pull(int x){ t[x].sum = t[t[x].ch[0]].sum ^ t[x].val ^ t[t[x].ch[1]].sum; }
void rev(int x){ swap(t[x].ch[0],t[x].ch[1]); t[x].rev^=1; }
void push(int x){ if(t[x].rev){ if(t[x].ch[0])rev(t[x].ch[0]); if(t[x].ch[1])rev(t[x].ch[1]); t[x].rev=false; } }
int dir(int x){ return t[t[x].par].ch[1]==x; }
void rotate(int x){
    int p=t[x].par, g=t[p].par, d=dir(x);
    if(!isRoot(p)) t[g].ch[dir(p)]=x;
    t[x].par=g;
    t[p].ch[d]=t[x].ch[d^1]; if(t[x].ch[d^1]) t[t[x].ch[d^1]].par=p;
    t[x].ch[d^1]=p; t[p].par=x; pull(p); pull(x);
}
void pushAll(int x){ if(!isRoot(x)) pushAll(t[x].par); push(x); }
void splay(int x){
    pushAll(x);
    while(!isRoot(x)){
        int p=t[x].par;
        if(!isRoot(p)) (dir(x)==dir(p))?rotate(p):rotate(x);
        rotate(x);
    }
}
int access(int x){
    int last=0;
    for(int y=x; y; y=t[y].par){ splay(y); t[y].ch[1]=last; pull(y); last=y; }
    splay(x); return last;
}
void makeRoot(int x){ access(x); rev(x); }
void link(int u,int v){ makeRoot(u); t[u].par=v; }                 // u-v 연결
void cut(int u,int v){ makeRoot(u); access(v); t[v].ch[0]=t[u].par=0; pull(v); }
int pathQuery(int u,int v){ makeRoot(u); access(v); return t[v].sum; } // 경로 xor 합

자주 하는 실수

• isRoot 처리. 보조 트리 루트(부모가 자신을 자식으로 두지 않는 노드)에서 회전을 멈춰야 한다. path-parent와 일반 부모를 구분하는 핵심.
• push 순서. splay 전에 루트→대상 경로의 lazy를 위에서 아래로 모두 push (pushAll).
• access의 right child 교체. t[y].ch[1]=last 로 preferred child를 갈아끼우고 pull.
• cut 전 인접 확인. 실제로 간선이 있는지 검증 후 cut. 없으면 트리가 깨진다.
• 집계 항등원. xor면 0, 합이면 0, 최대면 \(-\infty\).

응용

HLD와의 선택

트리가 정적이면 HLD+세그먼트 트리가 상수가 작아 유리하다. 간선이 바뀌면 LCT가 사실상 유일한 \(O(\log n)\) 선택지다. subtree 질의까지 필요하면 LCT에 light child 집계를 추가하는 확장이 필요하다.