# 트리 심화: 분할 기법

기본 트리 문제는 DFS 한 번으로 깊이, 부모, subtree 크기를 구하면 풀리는 경우가 많습니다. 심화 트리 문제는 한 단계 더 나아가서 트리를 **다른 순서나 더 작은 조각**으로 바꿔 다룹니다.

이 문서에서는 아래 도구를 연결해서 봅니다.

```text
Euler Tour: subtree를 배열 구간으로 바꾼다.
LCA: 두 정점 사이 경로의 교차점을 빠르게 찾는다.
Centroid Decomposition: 트리를 균형 있게 쪼갠다.
Heavy-Light Decomposition: 경로를 몇 개의 배열 구간으로 쪼갠다.
Small-to-large: subtree 정보를 큰 쪽에 작은 쪽을 합치며 관리한다.
```

## 언제 심화 기법이 필요한가

트리에서 질의가 한 번만 나오면 DFS나 BFS로 충분한 경우가 많습니다. 하지만 아래 조건이 붙으면 전처리와 자료구조가 필요합니다.

| 문제 형태 | 자주 쓰는 도구 |
| --- | --- |
| subtree 전체에 업데이트/질의 | Euler Tour + Fenwick Tree 또는 Segment Tree |
| 두 정점 사이 경로 질의 | LCA, Heavy-Light Decomposition |
| 가장 가까운 표시 정점, 거리 기반 동적 질의 | Centroid Decomposition |
| 각 subtree의 색/값 종류 집계 | small-to-large, DSU on tree |
| 여러 중요 정점만 압축해서 처리 | Virtual Tree |

핵심은 트리를 그대로 보지 않는 것입니다. subtree는 배열의 연속 구간으로, 경로는 여러 heavy path 구간으로, 거리 질의는 센트로이드 조상들의 후보 비교로 바꿉니다.

## Euler Tour

DFS로 정점을 처음 방문한 시간을 `tin[u]`, subtree를 빠져나온 직후를 `tout[u]`라고 합시다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
// 각 독립 예제의 vector는 사용 전에 정점 수 n으로 resize한다.
int timer = 0;
vector<int> tin, tout, order;

void dfsEuler(int u, int parent, const vector<vector<int>>& tree) {
    tin[u] = timer++;
    order.push_back(u);

    for (int v : tree[u]) {
        if (v == parent) continue;
        dfsEuler(v, u, tree);
    }

    tout[u] = timer;
}
```

그러면 `u`의 subtree에 있는 정점들은 Euler 배열에서 아래 구간에 모입니다.

```text
[tin[u], tout[u])
```

이 성질 덕분에 subtree 합, subtree 색칠, subtree 최댓값 같은 문제를 배열 구간 질의로 바꿀 수 있습니다.

양 끝을 포함하는 구간 API에서는 `segmentTree.query(tin[u], tout[u] - 1)`로 합을 구합니다.

주의할 점은 Euler Tour가 subtree에는 강하지만, 임의의 두 정점 사이 경로는 일반적으로 한 구간이 아니라는 것입니다. 경로 질의에는 Heavy-Light Decomposition이 더 자연스럽습니다.

## LCA

LCA(Lowest Common Ancestor)는 두 정점의 가장 가까운 공통 조상입니다. 두 정점 사이 거리도 LCA로 계산할 수 있습니다.

```text
dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]
```

Binary Lifting은 각 정점의 `2^k`번째 조상을 미리 저장합니다.

```cpp
const int LOG = 20;
vector<array<int, LOG>> up;
vector<int> depth;

void dfsLca(int u, int parent, const vector<vector<int>>& tree) {
    up[u][0] = parent;
    for (int k = 1; k < LOG; ++k) {
        up[u][k] = up[up[u][k - 1]][k - 1];
    }

    for (int v : tree[u]) {
        if (v == parent) continue;
        depth[v] = depth[u] + 1;
        dfsLca(v, u, tree);
    }
}

int lift(int u, int diff) {
    for (int k = 0; k < LOG; ++k) {
        if (diff & (1 << k)) {
            u = up[u][k];
        }
    }
    return u;
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = lift(a, depth[a] - depth[b]);
    if (a == b) return a;

    for (int k = LOG - 1; k >= 0; --k) {
        if (up[a][k] != up[b][k]) {
            a = up[a][k];
            b = up[b][k];
        }
    }
    return up[a][0];
}
```

`LOG`는 `2^LOG > n`이 되도록 잡습니다. `n <= 200000`이면 `LOG = 18`이면 충분하지만, 여유 있게 `20` 또는 `21`을 쓰는 식입니다.

루트의 부모는 보통 자기 자신으로 둡니다. 예를 들어 `root = 0`이면 아래처럼 호출합니다. 루트 부모를 `-1`로 둘 경우에는 `up[u][k]`를 계산할 때 `-1` 접근을 막는 별도 처리가 필요합니다.

```cpp
depth[0] = 0;
dfsLca(0, 0, tree);
```

## 센트로이드 분할

센트로이드는 제거했을 때 남는 모든 컴포넌트 크기가 전체의 절반 이하인 정점입니다. 센트로이드 분할은 이 정점을 루트처럼 잡아 트리를 균형 있게 쪼개고, 각 조각에서 다시 센트로이드를 찾는 방법입니다.

분할 결과는 원래 트리가 아니라 **센트로이드 트리**입니다.

```text
원래 트리: 거리와 경로가 정의된 실제 입력 트리
센트로이드 트리: 분할 순서를 나타내는 보조 트리
```

기본 빌드는 아래처럼 진행합니다.

```cpp
vector<int> sub;
vector<int> blocked;
vector<int> centroidParent;

int calcSize(int u, int parent, const vector<vector<int>>& tree) {
    sub[u] = 1;
    for (int v : tree[u]) {
        if (v == parent || blocked[v]) continue;
        sub[u] += calcSize(v, u, tree);
    }
    return sub[u];
}

int findCentroid(int u, int parent, int total, const vector<vector<int>>& tree) {
    for (int v : tree[u]) {
        if (v == parent || blocked[v]) continue;
        if (sub[v] * 2 > total) {
            return findCentroid(v, u, total, tree);
        }
    }
    return u;
}

void buildCentroidTree(int entry, int parent, const vector<vector<int>>& tree) {
    int total = calcSize(entry, -1, tree);
    int c = findCentroid(entry, -1, total, tree);

    centroidParent[c] = parent;
    blocked[c] = 1;

    for (int v : tree[c]) {
        if (blocked[v]) continue;
        buildCentroidTree(v, c, tree);
    }
}
```

각 단계에서 조각 크기가 절반 이하로 줄어들기 때문에 센트로이드 트리의 높이는 `O(log n)`입니다.

## 센트로이드 분할로 거리 질의 처리하기

대표 문제는 동적으로 색칠되는 정점 중 `u`에서 가장 가까운 정점까지의 거리를 묻는 형태입니다.

```text
update(x): x를 빨간 정점으로 표시한다.
query(u): u에서 가장 가까운 빨간 정점까지의 거리를 구한다.
```

각 정점은 센트로이드 트리에서 자기 조상 센트로이드들을 `O(log n)`개만 가집니다. 빨간 정점 `x`를 추가할 때, `x`의 모든 센트로이드 조상 `c`에 대해 `best[c] = min(best[c], dist(x, c))`를 갱신합니다.

질의 `u`도 자기 센트로이드 조상 `c`들을 보면서 아래 값을 비교합니다.

```text
best[c] + dist(u, c)
```

코드 모양은 단순합니다. `distance(a, b)`는 LCA로 계산한다고 가정합니다.

```cpp
const int INF = 1e9;
vector<int> best; // best.assign(n, INF), centroidParent 루트는 -1
// calcSize 전에 sub/blocked/centroidParent를 n칸 초기화한다.

void paintRed(int x) {
    for (int c = x; c != -1; c = centroidParent[c]) {
        best[c] = min(best[c], distance(x, c));
    }
}

int nearestRed(int u) {
    int answer = INF;
    for (int c = u; c != -1; c = centroidParent[c]) {
        answer = min(answer, best[c] + distance(u, c));
    }
    return answer;
}
```

각 update/query는 센트로이드 조상 수만큼만 보므로 `O(log n * cost(distance))`입니다. LCA 거리 계산이 `O(log n)`이면 전체는 `O(log^2 n)`, 거리 값을 분할 과정에서 미리 저장하면 `O(log n)`까지 줄일 수 있습니다.

센트로이드 분할은 "거리 후보를 모든 정점에서 찾는 대신, 균형 분할의 조상 센트로이드들만 본다"는 관점으로 이해하면 됩니다.

## Heavy-Light Decomposition

Heavy-Light Decomposition, 줄여서 HLD는 트리의 경로를 배열 구간 몇 개로 나누는 기법입니다.

각 정점에서 subtree 크기가 가장 큰 자식을 heavy child로 고릅니다. heavy edge를 따라 이어지는 경로를 하나의 chain으로 만들면, 임의의 루트-정점 경로는 `O(log n)`개의 chain 조각으로 나뉩니다.

먼저 부모, 깊이, subtree 크기, heavy child를 구합니다.

```cpp
vector<int> parent, depth, heavy, head, pos, sub;
int currentPos = 0;

int dfsHld(int u, const vector<vector<int>>& tree) {
    sub[u] = 1;
    int bestSize = 0;

    for (int v : tree[u]) {
        if (v == parent[u]) continue;
        parent[v] = u;
        depth[v] = depth[u] + 1;
        int childSize = dfsHld(v, tree);
        sub[u] += childSize;

        if (childSize > bestSize) {
            bestSize = childSize;
            heavy[u] = v;
        }
    }
    return sub[u];
}
```

그다음 heavy child는 같은 chain으로, light child는 새 chain의 head로 내려갑니다.

```cpp
void decompose(int u, int chainHead, const vector<vector<int>>& tree) {
    head[u] = chainHead;
    pos[u] = currentPos++;

    if (heavy[u] != -1) {
        decompose(heavy[u], chainHead, tree);
    }

    for (int v : tree[u]) {
        if (v == parent[u] || v == heavy[u]) continue;
        decompose(v, v, tree);
    }
}
```

처음 빌드할 때는 모든 배열을 초기화하고, 루트의 부모를 자기 자신으로 둔 뒤 시작합니다.

```cpp
void buildHld(const vector<vector<int>>& tree, int root = 0) {
    int n = (int)tree.size();

    parent.assign(n, -1);
    depth.assign(n, 0);
    heavy.assign(n, -1);
    head.assign(n, -1);
    pos.assign(n, -1);
    sub.assign(n, 0);

    currentPos = 0;
    parent[root] = root;
    dfsHld(root, tree);
    decompose(root, root, tree);
}
```

`pos[u]`는 정점 `u`가 세그먼트 트리 배열에서 차지하는 위치입니다. 같은 chain에 있는 정점들은 `pos`가 연속으로 배치됩니다.

## HLD로 경로 질의 처리하기

두 정점 `a`, `b` 사이 경로를 처리할 때는 두 정점이 같은 chain에 올 때까지 chain head가 더 깊은 쪽을 위로 올립니다.

```cpp
long long queryPath(int a, int b) {
    long long result = 0;

    while (head[a] != head[b]) {
        if (depth[head[a]] < depth[head[b]]) {
            swap(a, b);
        }

        result += segmentTree.query(pos[head[a]], pos[a]);
        a = parent[head[a]];
    }

    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    result += segmentTree.query(pos[a], pos[b]);
    return result;
}
```

경로 위의 값 갱신도 같은 방식으로 구간 업데이트를 여러 번 호출하면 됩니다.

```cpp
void updatePath(int a, int b, long long delta) {
    while (head[a] != head[b]) {
        if (depth[head[a]] < depth[head[b]]) {
            swap(a, b);
        }

        segmentTree.rangeAdd(pos[head[a]], pos[a], delta);
        a = parent[head[a]];
    }

    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    segmentTree.rangeAdd(pos[a], pos[b], delta);
}
```

정점 값 문제라면 위 코드처럼 양 끝을 포함합니다. 간선 값 문제라면 보통 간선 값을 더 깊은 정점 쪽 위치에 저장하므로 마지막 구간에서 `pos[a] + 1`부터 처리해야 할 때가 많습니다.

```text
정점 값 경로: [pos[lca], pos[child]]
간선 값 경로: [pos[lca] + 1, pos[child]]
```

## HLD와 Euler Tour의 관계

HLD의 `pos` 배열은 heavy path를 우선해서 정점을 배치합니다. 그래도 DFS 순서이기 때문에 subtree가 연속 구간이 되도록 구현할 수 있습니다.

HLD 순서에서 subtree 질의는 `segmentTree.query(pos[u], pos[u] + sub[u] - 1)`입니다.

따라서 같은 세그먼트 트리로 아래 두 종류의 질의를 함께 처리할 수 있습니다.

| 질의 | 구간 변환 |
| --- | --- |
| subtree 질의 | `[pos[u], pos[u] + sub[u] - 1]` |
| 경로 질의 | HLD chain 구간 여러 개 |

다만 모든 HLD 구현이 subtree 연속성을 보장하는 것은 아닙니다. 위 코드처럼 정점을 처음 방문할 때 `pos`를 부여하고 모든 자식을 이어서 방문해야 subtree 구간이 연속이 됩니다.

## small-to-large

subtree마다 색 종류 수, 값 빈도, 문자열 집합 같은 것을 모아야 할 때 모든 subtree를 매번 새로 만들면 `O(n^2)`가 됩니다. small-to-large는 작은 컨테이너를 큰 컨테이너에 합쳐 전체 이동 횟수를 줄이는 기법입니다.

```cpp
vector<unordered_map<int, int>*> bag;
vector<int> distinctCount; // n칸으로 초기화, 각 subtree의 답을 따로 보관

void dfsSmallToLarge(int u, int parent, const vector<vector<int>>& tree, const vector<int>& color) {
    int heavyChild = -1;
    for (int v : tree[u]) {
        if (v == parent) continue;
        dfsSmallToLarge(v, u, tree, color);
        if (heavyChild == -1 || bag[v]->size() > bag[heavyChild]->size()) {
            heavyChild = v;
        }
    }

    if (heavyChild == -1) {
        bag[u] = new unordered_map<int, int>();
    } else {
        bag[u] = bag[heavyChild];
    }

    (*bag[u])[color[u]]++;

    for (int v : tree[u]) {
        if (v == parent || v == heavyChild) continue;
        for (auto [key, value] : *bag[v]) {
            (*bag[u])[key] += value;
        }
        delete bag[v]; // 하위 bag 포인터는 재사용하지 않는다.
        bag[v] = nullptr;
    }
    distinctCount[u] = (int)bag[u]->size();
}
```

합쳐진 뒤 자식 bag의 내용은 부모에 흡수되므로 자식별 답은 `distinctCount`에서 읽습니다. 모든 작업이 끝나면 `delete bag[root]`로 마지막 map만 해제합니다. 중복 key가 합쳐져 사라지는 비용까지 상각하면 총 원소 처리량은 `O(n log n)`이며, unordered_map 연산은 평균 시간 기준입니다.

실전에서는 메모리 관리가 번거로우면 포인터 대신 `vector<map<int, int>>`와 swap을 쓰기도 합니다.

## 시간 복잡도

| 기법 | 전처리 | 질의/업데이트 |
| --- | --- | --- |
| Euler Tour + Fenwick/Segment Tree | `O(n)` | `O(log n)` |
| LCA binary lifting | `O(n log n)` | `O(log n)` |
| Centroid Decomposition | `O(n log n)` | 보통 `O(log n)` |
| Heavy-Light Decomposition | `O(n)` | 경로당 `O(log^2 n)` 또는 구현에 따라 `O(log n)` |
| small-to-large | 전체 `O(n log n)` 수준 | subtree 집계 문제에 따라 다름 |