탑 트리

동기: 경로와 서브트리를 동시에

Link-Cut Tree는 경로 질의에 강하지만 서브트리 합 같은 질의는 어색하다. 탑 트리(Top Tree) 는 트리를 클러스터(cluster) 계층으로 추상화해 경로·서브트리 질의를 한 틀에서 다룬다.

클러스터와 경계 정점

탑 트리의 단위는 클러스터: 원래 트리의 연결된 부분 그래프로, 외부와 닿는 경계 정점(boundary vertex) 이 최대 2개다.

• 베이스 클러스터: 원래 트리의 간선 하나.
• 두 클러스터를 합치는 두 연산:
• compress: 경계 정점을 공유하는 두 경로형 클러스터를, 그 중간 정점을 내부로 흡수 하며 합침.
• rake: 한 클러스터를 다른 클러스터의 경계에 매달아 흡수(서브트리 방향).

두 경계 = 두 손잡이

각 클러스터는 두 경계 정점 \((a, b)\)를 손잡이로 노출한다. compress는 \(a - m - b\)를 \(a - b\)로(중간 \(m\) 흡수), rake는 매다는 쪽 경계를 없앤다. 트리 전체는 결국 하나의 루트 클러스터로 수축된다.

이 수축 과정은 트리를 균형 잡힌 계층으로 만들어, \(O(\log n)\) 깊이를 보장한다(셀프-밸런싱: 무작위/병렬 수축 또는 LCT 위에 얹는 방식).

집계(aggregate)의 정의

클러스터마다 사용자 정의 정보를 둔다. 합치는 규칙을 두 가지로 준다.

• merge_compress(L, R, m): 경로 정보 결합(예: 경로 합/최댓값, 중간 정점 \(m\)의 기여 포함).
• merge_rake(L, R): 서브트리 정보 결합(매달린 가지의 기여).

이 두 함수가 결합법칙을 만족하면 어떤 순서로 수축해도 같은 답이 나온다.

무엇을 풀 수 있나

expose 연산

특정 정점(또는 두 정점)을 루트 클러스터의 경계로 끌어올리는 expose가 핵심 인터페이스다. expose 후에는 원하는 경로/서브트리가 루트 클러스터의 집계로 즉시 읽힌다. 한 번의 expose는 \(O(\log n)\) 클러스터를 재구성한다.

복잡도

모든 연산(link, cut, expose, 질의)이 amortized 또는 worst-case \(O(\log n)\). 상수는 LCT보다 크지만, 경로·서브트리·트리 전역 질의를 동시에 지원하는 범용성이 강점이다.

다음 강의에서 LCT 위에 rake를 얹는 실전 설계와 예제 집계를 본다.

구현 전략: LCT + rake 트리

탑 트리를 처음부터 구현하긴 무겁다. 실전에서 자주 쓰는 구성:

1. selected/preferred 경로: LCT처럼 splay로 관리(compress 담당).
2. rake 트리: 각 경로 정점에 매달린 가벼운 서브트리들을 또 다른 균형 BST(보통 멀티셋/보조 splay)로 묶음.

즉 "compress = LCT, rake = 보조 BST"의 2층 구조다.

집계 인터페이스(개념 코드)

struct Path {              // compress용 경로 집계
    long long sum;         // 경로 가중치 합
    long long best;        // 경로 최댓값
};
struct Sub {               // rake용 서브트리 집계
    long long sum;         // 서브트리 가중치 합
};

Path mergeCompress(const Path& a, const Path& b, long long mid) {
    return { a.sum + mid + b.sum, max({a.best, mid, b.best}) };
}
Sub mergeRake(const Sub& a, const Sub& b) {
    return { a.sum + b.sum };
}

mid는 compress가 흡수하는 중간 정점의 기여(서브트리 합 포함)다.

정점 갱신

정점 \(v\)의 가중치를 바꾸면:

void update(int v, long long w) {
    access(v);             // v를 preferred 경로 루트로
    val[v] = w;
    pull(v);               // 경로/서브트리 집계 재계산 (위로 전파)
}

access는 LCT의 expose에 해당하며 \(O(\log n)\).

예제 1: 트리 위 경로 최댓값 + 정점 갱신

mergeCompress의 best만 읽으면 된다. expose(u, v) 후 루트 경로 클러스터의 best가 답.

예제 2: 서브트리 합 질의

정점 \(v\)를 루트로 본 서브트리 합은, \(v\)를 access한 뒤 \(v\)에 매달린 rake 집계 + \(v\) 자신을 더한 값.

long long subtreeSum(int v) {
    access(v);
    return val[v] + rakeSum[v];   // rakeSum: v에 매달린 가지들의 합
}

루트가 바뀌는(rerooting) 질의는 makeRoot(v)(경로 뒤집기 lazy)로 처리한다.

예제 3: 동적 트리 지름

각 클러스터에 (diameter, 두 경계에서의 최대 깊이쌍)을 저장하고, merge 시 양쪽 깊이를 합쳐 경로를 잇는 후보를 비교한다. link/cut 후에도 \(O(\log n)\)에 전역 지름을 유지한다.

struct Diam {
    long long dia;        // 클러스터 내부 최대 거리
    long long up, down;   // 두 경계에서의 최대 깊이
    long long len;        // 두 경계 사이 경로 길이
};
Diam mergeC(const Diam& a, const Diam& b) {
    Diam r;
    r.len  = a.len + b.len;
    r.up   = max(a.up, a.len + b.up);
    r.down = max(b.down, b.len + a.down);
    r.dia  = max({a.dia, b.dia, a.down + b.up});
    return r;
}

함정 정리

• merge 함수의 결합법칙과 방향(좌/우 경계) 일관성. compress는 비대칭이라 좌우 구분이 필수.
• lazy(경로 뒤집기, 구간 덧셈)는 compress 경로에만 단순 적용; rake 쪽 전파 규칙을 별도로 정의.
• rake 트리도 균형이어야 전체 \(O(\log n)\) 유지.

연습: link/cut + 정점 갱신 + 경로 최댓값 + 서브트리 합을 모두 요구하는 종합 문제로 위 인터페이스를 검증하라. 모든 연산 amortized \(O(\log n)\).