김신건의 로그
📁 algorithm

Dynamic Tree (Link/Cut Tree, Euler Tour Tree, Top Tree)

· 수정 · 📖 약 5분 · 1,711자/단어 #algorithm #data-structure #tree #dynamic-tree #link-cut-tree
Link-Cut Tree, Dynamic Tree, Link/Cut Tree, LCT, Euler Tour Tree, ETT, Top Tree, 동적 트리

정의

Dynamic Tree 는 트리에 간선 추가 (link) / 제거 (cut) 가 섞이는 환경에서 경로 / 서브트리 집계 쿼리 를 O(log N) 에 처리하는 자료구조 가족. 대표적으로 Link/Cut Tree, Euler Tour Tree, Top Tree.

기본 Tree DP / Euler Tour + Segment Tree 는 트리 모양이 고정일 때만 동작. Dynamic Tree 는 Forest 의 모양이 매 쿼리마다 바뀌어도 답을 빠르게 갱신.

문제 상황과 동기

트리의 모양이 link/cut 연산으로 계속 바뀌는 환경에서 경로 집계나 서브트리 집계를 O(log N) 시간에 처리해야 하는 상황. 예를 들어:

  • 동적 MST: 간선 삽입/삭제가 계속되는 그래프에서 MST 유지
  • 동적 연결성: 두 정점이 같은 트리에 속하는지 쿼리
  • 경로 쿼리: link/cut 이 섞인 상황에서 u-v 경로의 합/최댓값

Naive 접근의 한계: 매 link/cut 마다 HLD 나 Euler Tour 를 재구성하면 O(N) 또는 O(N log N). 10⁵ 개 쿼리에 TLE.

핵심 아이디어: 트리를 작은 조각 (path 또는 sequence) 으로 분해해 BBST 로 유지하고, link/cut 을 BBST 의 split/merge 로 처리. 각 조각의 집계 값을 BBST 노드에 저장하면 경로 쿼리도 O(log N). LCT 는 preferred path decomposition, ETT 는 Euler tour sequence, Top Tree 는 cluster decomposition 으로 이를 구현.

시각화

구현

Dynamic Tree 는 세 가지 주요 구현이 있다. 가장 널리 쓰이는 Link/Cut Tree (LCT) 를 중심으로 설명.

Link/Cut Tree (LCT)

Preferred path decomposition + Splay Tree. 각 정점에서 부모로 향하는 preferred edge 를 splay tree 로 묶어 경로 집계 O(log N).

// Link/Cut Tree (LCT), 경로 집계 O(log N)
#include <algorithm>
using namespace std;

struct Node {
    int p, ch[2];    // 부모, 좌/우 자식 (splay tree)
    bool rev;        // lazy reverse
    long long val;   // 정점 값
    long long sum;   // 서브트리 합
};

const int MAXN = 100005;
Node t[MAXN];

inline bool is_root(int x) {
    return t[t[x].p].ch[0] != x && t[t[x].p].ch[1] != x;
}

void push(int x) {
    if (t[x].rev) {
        swap(t[x].ch[0], t[x].ch[1]);
        for (int i = 0; i < 2; i++) {
            if (t[x].ch[i]) t[t[x].ch[i]].rev ^= 1;
        }
        t[x].rev = false;
    }
}

void pull(int x) {
    t[x].sum = t[x].val;
    for (int i = 0; i < 2; i++) {
        if (t[x].ch[i]) t[x].sum += t[t[x].ch[i]].sum;
    }
}

void rotate(int x) {
    int p = t[x].p, g = t[p].p;
    push(p); push(x);
    bool is_r = (t[p].ch[1] == x);
    if (!is_root(p)) t[g].ch[t[g].ch[1] == p] = x;
    t[x].p = g;
    t[p].ch[is_r] = t[x].ch[!is_r];
    if (t[x].ch[!is_r]) t[t[x].ch[!is_r]].p = p;
    t[x].ch[!is_r] = p;
    t[p].p = x;
    pull(p); pull(x);
}

void splay(int x) {
    while (!is_root(x)) {
        int p = t[x].p, g = t[p].p;
        if (!is_root(p)) push(g);
        push(p); push(x);
        if (!is_root(p)) {
            if ((t[g].ch[0] == p) == (t[p].ch[0] == x)) rotate(p);
            else rotate(x);
        }
        rotate(x);
    }
    push(x);
}

void access(int v) {
    // v 에서 루트까지 preferred path 생성
    for (int x = v, last = 0; x; last = x, x = t[x].p) {
        splay(x);
        t[x].ch[1] = last;
        pull(x);
    }
    splay(v);
}

void make_root(int v) {
    access(v);
    t[v].rev ^= 1;
    push(v);
}

void link(int u, int v) {
    make_root(u);
    access(v);
    t[u].p = v;
}

void cut(int u, int v) {
    make_root(u);
    access(v);
    t[v].ch[0] = t[u].p = 0;
    pull(v);
}

long long path_sum(int u, int v) {
    make_root(u);
    access(v);
    return t[v].sum;
}

시간 복잡도: 모든 연산 amortized O(log N).

구현 팁:

  1. access 함수: LCT 의 핵심. 잘못 구현하면 전부 깨짐. 검증된 레퍼런스 복붙 권장.
  2. push down: splay 회전 전 반드시 lazy 를 push. rev 빼먹으면 WA.
  3. is_root: path parent 와 splay parent 구분. t[p].ch[0] != x && t[p].ch[1] != x 으로 판정.

Euler Tour Tree (ETT) 골격

트리의 오일러 투어 시퀀스를 Treap 으로 유지. 서브트리 집계에 강함.

(Treap 기반 ETT 의사코드)

struct ETTNode {
    int vertex;       // 원래 정점 번호
    bool is_enter;    // true: enter, false: exit
    // Treap fields: priority, left, right, size, sum
};

link(u, v):
    u_seq = extract_subtree(u)
    v_seq = extract_subtree(v)
    merge(v_seq, u_seq, v_seq)  // v 의 enter/exit 사이에 u 삽입

cut(u, v):
    u 의 enter/exit 구간을 split 으로 분리

subtree_sum(v):
    v 의 enter ~ exit 구간 합

실제 구현은 Treap split/merge + enter/exit 관리로 300+ 줄.

Top Tree

가장 일반적. 트리 cluster 를 BBST 로. 경로 + 서브트리 모두 O(log N). 구현 난도 최상.

Link/Cut Tree (LCT)

[Sleator-Tarjan 1983]. Preferred Path Decomposition + Splay Tree 기반.

핵심 동작

각 정점 v 는 부모로 향하는 preferred edge 를 하나만 가질 수 있다. Preferred edge 로 연결된 체인을 하나의 Splay Tree 로 표현. 나머지 간선은 path parent pointer 로.

  • access(v): v 에서 루트까지 preferred path 를 갱신. 이전 preferred child 를 끊고 v 로 이어진 경로를 새로운 preferred path 로.
  • make_root(v): v 를 루트로. access(v) 후 splay 한 뒤 lazy reverse 로 방향 뒤집기.
  • link(u, v): v 를 루트로 만든 뒤 u 의 자식으로 연결.
  • cut(u, v): u-v 를 끊기. make_root(u) 후 access(v) 하면 u 가 v 의 splay tree 맨 앞. 이 간선을 끊으면 됨.
  • path_sum(u, v): make_root(u), access(v) 후 v 의 splay tree 전체 합.

잘하는 것: 경로 집계 (path sum, path max), 두 노드 LCA, 동적 MST
약한 것: 서브트리 집계 (직접 못 함, Top Tree 또는 ETT 필요)

Euler Tour Tree (ETT)

[Henzinger-King 1995]. 트리의 오일러 투어 시퀀스 를 BBST (Treap 이 일반적) 로 들고 다님.

핵심 아이디어

트리를 DFS 순서로 방문하면서 각 정점을 enter 와 exit 시점에 두 번 기록. 이 시퀀스를 BBST 로 유지하면:

  • link(u, v): u 의 시퀀스와 v 의 시퀀스를 잘라 이음
  • cut(u, v): u-v 간선에 해당하는 구간을 split
  • subtree_sum(v): v 의 enter ~ exit 구간의 합

시퀀스 길이 = 2(N-1). enter/exit 쌍 사이가 서브트리.

잘하는 것: 서브트리 집계 약한 것: 경로 집계 (직접 못 함)

작은 예시

트리:
    1
   / \
  2   3

Euler tour sequence (enter/exit):
  [1e, 2e, 2x, 3e, 3x, 1x]

노드 1 의 서브트리: 1e ~ 1x 전체 (인덱스 0 ~ 5)
노드 2 의 서브트리: 2e ~ 2x (인덱스 1 ~ 2)

이 시퀀스를 Treap/BBST 로 들고, split/merge 로 link/cut 처리.

Top Tree

가장 일반적. 트리 위의 cluster 라는 추상 구조를 BBST 로. 경로 집계 + 서브트리 집계 + 동적 모양 변경을 모두 O(log N) 에.

  • 구현이 가장 무거움
  • 적용 가능 문제 가장 넓음
  • ETT + LCT 의 상위 호환

비교

자료구조경로 쿼리서브트리 쿼리구현 난도메모리
LCTOK어려움중간O(N)
ETT어려움OK중간O(N)
Top TreeOKOK매우 어려움O(N)

공통 응용

동적 그래프 연결성 (Holm-Lichtenberg-Thorup)

ETT 가 핵심. 간선 삽입/삭제 + 두 정점 연결 여부 확인을 amortized O(log² N).

동적 MST

LCT + 가중치 max. 새 간선 추가 시 형성되는 사이클 의 최대 가중치 간선과 비교.

경로 합 + 부분 갱신

LCT 의 가장 기본 응용.

함정

1. access 함수 구현

LCT 의 가장 중요한 함수. 잘못 구현하면 전부 깨짐. 검증된 레퍼런스 (imeimi, koosaga) 복붙 권장.

2. push down 누락

splay 회전 / split / merge 전후로 lazy 를 push down. ETT 의 lazy reverse 도 마찬가지.

3. ETT 의 시퀀스 정의

각 노드를 enter / exit 두 번 등장시키는 정의가 표준. enter 만 하면 서브트리 구간이 정의 안 됨.

4. Top Tree 의 학습 곡선

PS 에서 직접 구현하는 일은 드물다. 필요하면 koosaga 의 InfoSSM 글을 참고해서 6 ~ 8 시간 안에 끝낼 각오로.

BOJ 연습 문제

공통

번호제목링크
BOJ 13539트리와 쿼리 11kokoa-lab

Link/Cut Tree

번호제목링크
BOJ 21973남극 탐험kokoa-lab
BOJ 10724판게아 2kokoa-lab
BOJ 18861가슴 속에 무엇인가kokoa-lab
BOJ 22906장난감 오렌지 만들기kokoa-lab
BOJ 18374함수의 맛kokoa-lab

Euler Tour Tree

번호제목링크
BOJ 27974트리와 쿼리 21kokoa-lab

Top Tree

번호제목링크
BOJ 17936트리와 쿼리 13kokoa-lab
BOJ 21728트리와 2개의 지름kokoa-lab

다른 출처 연습 문제

출처제목링크
Library CheckerDynamic Tree Vertex Add Path Sumhttps://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum
Library CheckerDynamic Tree Vertex Set Path Compositehttps://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite
Library CheckerDynamic Tree Vertex Add Subtree Sumhttps://judge.yosupo.jp/problem/dynamic_tree_vertex_add_subtree_sum
Library CheckerDynamic Tree Subtree Add Subtree Sumhttps://judge.yosupo.jp/problem/dynamic_tree_subtree_add_subtree_sum

참고

이 개념을 다룬 위키 페이지 (10)

💬 댓글

사이트 검색 / 명령어

검색

스크롤 = 확대/축소 · 드래그 = 이동 · 0 = 원래 크기 · ESC = 닫기