헤비-라이트 분할

무엇을 해결하나

트리에서 "정점 \(u\)와 \(v\) 사이 경로상의 합/최댓값을 구하라", "경로상 모든 정점에
\(x\)를 더하라" 같은 경로 질의·갱신을 빠르게 처리하는 기법이 헤비-라이트
분할(HLD) 이다. 단순히 LCA까지 한 칸씩 올라가면 한 질의에 \(O(N)\)이 들 수
있는데, HLD는 이를 \(O(\log^2 N)\)으로 줄인다.

헤비 간선과 라이트 간선

각 정점에서 서브트리 크기가 가장 큰 자식으로 가는 간선을 헤비 간선,
나머지를 라이트 간선이라 한다.

핵심 보조정리: 루트에서 임의의 정점까지 내려가는 동안 라이트 간선은 최대
\(O(\log N)\)번 거친다.

이유는 라이트 간선을 한 번 탈 때마다 서브트리 크기가 절반 미만으로 줄기
때문이다(헤비가 아니므로 그 자식 서브트리는 부모 서브트리의 절반 이하). 절반씩
줄어드니 \(\log N\)번이면 끝난다.

사슬(chain)로 묶기

헤비 간선으로 이어진 정점들을 하나의 사슬로 묶는다. 그러면 트리 전체가
\(O(\log N)\) 깊이의 사슬 구조로 분해된다. 각 사슬 안의 정점들에게 연속된
번호(DFS 순서) 를 부여하면, 한 사슬 위의 구간이 배열의 연속 구간이 된다.
여기에 세그먼트 트리(필요하면 lazy)를 얹으면 사슬 내 구간 질의/갱신이
\(O(\log N)\)이다.

경로 질의 처리

\(u \to v\) 경로를 처리할 때, 두 정점 중 사슬 머리(head)가 더 깊은 쪽을 그 사슬
머리까지 한 번에 점프시키며 그 구간을 세그 트리로 질의한다. 같은 사슬에 올
때까지 반복하면, 경로가 \(O(\log N)\)개의 사슬 구간으로 쪼개진다. 각 구간
질의가 \(O(\log N)\)이므로 한 경로 질의가 \(O(\log^2 N)\)이다.

$$ \underbrace{O(\log N)}_{\text{사슬 점프 횟수}} \times \underbrace{O(\log N)}_{\text{세그 트리 질의}} = O(\log^2 N) $$

정점 vs 간선 가중치

가중치가 간선에 있으면, 각 간선을 그 자식 정점에 귀속시키고 경로 질의
시 LCA 정점은 제외한다. 이 한 가지 처리만 정확히 하면 정점 버전과 거의 같다.

HLD 구축

두 번의 DFS로 (1) 서브트리 크기와 헤비 자식, (2) 사슬 머리·DFS 순서(pos)를
계산한다. 그 위에 세그먼트 트리를 얹는다.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;

vector<int> g[MAXN];
int sz[MAXN], dep[MAXN], par[MAXN], heavy[MAXN];
int head_[MAXN], pos_[MAXN], cur_pos = 0;
int n;

int dfs_size(int u, int p) {     // 서브트리 크기, 헤비 자식
    sz[u] = 1; heavy[u] = -1; par[u] = p;
    int max_c = 0;
    for (int v : g[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        int c = dfs_size(v, u);
        sz[u] += c;
        if (c > max_c) { max_c = c; heavy[u] = v; }
    }
    return sz[u];
}
void decompose(int u, int h) {   // 사슬 머리 h, 연속 번호 부여
    head_[u] = h; pos_[u] = cur_pos++;
    if (heavy[u] != -1) decompose(heavy[u], h);          // 헤비 먼저
    for (int v : g[u]) if (v != par[u] && v != heavy[u])
        decompose(v, v);                                  // 라이트는 새 사슬
}

// seg_query(l, r): 배열 구간 [l, r]에 대한 세그 트리 질의(별도 구현)
long long seg_query(int l, int r);

long long path_query(int u, int v) {
    long long res = 0;
    while (head_[u] != head_[v]) {       // 다른 사슬이면
        if (dep[head_[u]] < dep[head_[v]]) swap(u, v);
        res += seg_query(pos_[head_[u]], pos_[u]);  // 사슬 머리까지
        u = par[head_[u]];                          // 한 칸 위 사슬로
    }
    if (dep[u] > dep[v]) swap(u, v);
    res += seg_query(pos_[u], pos_[v]);  // 같은 사슬 구간
    return res;
}

호출 순서는 dep[0]=0; dfs_size(root, -1); decompose(root, root);이고, 세그
트리는 pos_로 매핑된 배열 위에 세운다. 갱신도 같은 방식으로 path_query
틀을 따라 seg_update를 호출하면 된다.

흔한 실수

• 헤비 자식 먼저 decompose — decompose에서 반드시 헤비 자식을 먼저
  처리해야 한 사슬이 연속 번호를 받는다. 순서가 바뀌면 사슬이 끊긴다.
• 라이트 점프 방향 — path_query에서 사슬 머리가 더 깊은 쪽을 위로
  올려야 한다. swap 조건의 부등호를 정확히 두자.
• 간선 가중치 처리 — 간선 버전은 LCA 정점을 질의에서 빼야 한다(pos_[u]+1
  부터). 빼먹으면 LCA 위 간선을 잘못 포함한다.
• 세그 트리 lazy — 경로 갱신이 있으면 lazy 세그 트리가 필요하다.

응용

HLD는 서브트리 질의(연속 구간)와 경로 질의(사슬 분해)를 같은 배열 위에서
함께 처리한다는 점이 강력하다. 더 일반적인 동적 트리에는 이후의 링크-컷
트리가 쓰이지만, 정적 트리의 경로 문제 대부분은 HLD로 충분하다.