186. Heavy-Light Decomposition

헤비-라이트 분할(Heavy-Light Decomposition, HLD)는 트리에서 경로와 관련된 다양한 쿼리를 처리하는 테크닉이다. 트리에서 다음과 같은 쿼리를 처리하는 문제를 생각해 보자.

• $1\ i\ c$: $i$번째 간선의 가중치를 $c$로 바꾼다.
• $2\ x\ y$: 정점 $x$와 $y$ 사이의 최단 경로가 포함하는 간선들의 가중치의 합을 출력한다.

정점이 $n$개인 트리에서 두 정점 사의의 최단 경로는 최대 $(n - 1)$개의 간선을 포함하므로 경로상의 간선을 하나씩 보는 방법은 당연히 너무 느리다. 이 문제점을 해결하기 위해 HLD는 간선을 그룹으로 묶은 다음 그룹을 한 번에 처리할 수 있게 한다. 이때 경로가 너무 많은 그룹을 지나면 간선을 그룹으로 묶는 의미가 없어지므로 어떤 경로를 선택하더라도 최소한의 그룹만 확인하면 되게 하는 것이 HLD에서 중요한 부분이다.

 

그러면 간선을 어떤 기준에 따라 분류하는지 알아보자. 이 테크닉의 이름인 Heavy-Light Decomposition에서 Heavy와 Light는 각각 Heavy Edge와 Light Edge를 의미하는데 이것이 간선의 분류와 연관이 있다. 리프가 아닌 각각의 정점마다 서브트리의 크기가 가장 큰 자식과 연결된 간선을 Heavy Edge, 나머지 간선들을 Light Edge로 두고^[각주:1] 트리에서 정점과 Heavy Edge들만 남기면 서로 만나지 않는 여러 개의 경로가 일부 리프를 제외한 모든 정점을 지나는 형태가 된다. 이 문장은 한번에 와닿지 않을 수 있으므로 예시를 통해 확인하기로 한다.

 

루트가 $6$번 정점일 때 $3$번 정점 쪽 서브트리의 크기가 $5$로 가장 크다. 따라서 $6$번 정점과 $3$번 정점을 연결하는 간선이 Heavy Edge가 되고 $6$번 정점과 $8$번, $4$번 정점을 연결하는 간선은 Light Edge가 된다. 만약 서브트리의 크기가 가장 큰 자식이 두 개 이상이면 아무거나 하나를 선택한다. 이런 식으로 Heavy Edge와 Light Edge를 분류하면 다음과 같다.

 

빨간색으로 표시된 간선들이 Heavy Edge이다. 이제 이 Heavy Edge로 연결된 정점들이 같은 그룹에 속한다고 하고 그룹을 분류해 보자. 정점을 그룹으로 분류하는 것은 경로의 관점에서 생각하면 간선을 그룹으로 분류하는 것과 큰 차이가 없다.

 

정점을 총 $7$개의 그룹으로 분류할 수 있다. 앞에서 어떤 경로를 선택하든 최소한의 그룹을 지나게 하는 것이 HLD의 중요한 부분이라고 했으므로 이 기준으로 정점을 분류했을 때 임의의 경로가 최대 몇 개의 그룹을 지나는지 계산해 보기로 한다. 경로의 양 끝점 $u$와 $v$에 대해 $\text{LCA}(u, v)$를 $w$라고 하면 정점 $u$와 $w$ 사이의 경로와 정점 $w$와 $v$ 사이의 경로를 따로 확인하는 것이 편하다. 먼저 임의의 형제 정점은 항상 서로 다른 정점에 속하므로 두 경로가 공통으로 지나는 그룹은 없다.

 

조상에서 자손으로 향하는 경로를 따라 이동할 때 정점이 속한 그룹이 중간에 바뀌었을 경우 서브트리의 크기는 절반 미만으로 줄어들 것이다. 서브트리의 크기가 절반 이상인 자식 정점으로 이동할 경우 Heavy Edge를 따라 이동하게 되어 그룹이 바뀌지 않기 때문이다. 또한 서브트리의 크기가 절반 미만으로 줄어드는 상황은 최대 $\lg (n + 1) - 1$번만 발생할 수 있다. 즉 이것이 경로를 따라 조상에서 자손으로 이동할 때 정점이 속한 그룹이 바뀌는 횟수의 상한이고, 트리에서 임의의 경로는 앞 문단에서 언급한 것과 같이 조상과 자손 사이의 경로 두 개를 합친 것으로 생각할 수 있으므로 그런 경로가 지나는 그룹의 수는 최대 $2 \lg (n + 1)$이 된다.

 

그룹을 어떤 식으로 한번에 처리할 수 있는지 알아보기 전에 Heavy Edge가 '가장 깊은 자손이 있는 자식  정점' 대신 '서브트리가 가장 큰 자식 정점'을 따라가는 이유를 알아보자. 이것은 확인해야 하는 그룹 수의 상한이 작은 방식을 선택한 것으로, 다음과 같은 형태의 트리에서 경로는 $\sqrt{2n}$개 정도의 그룹까지도 지날 수 있다.

따라서 확인해야 하는 그룹 수의 상한이 훨씬 높아지기 때문에 이 방식은 쓰지 않는다.

 

이제 그룹을 한번에 처리하는 방법을 알아볼 차례이다. 그룹을 처리하는 방법은 하나로 정해져 있지는 않으나 세그먼트 트리가 가장 자주 사용된다. 즉 각 정점의 정보를 세그먼트 트리의 리프에 저장한 다음 구간 쿼리로 그룹을 한번에 처리하는 것이다. 이렇게 하기 위해서는 같은 그룹에 속한 정점의 번호가 연속적이어야 하는데, 이것은 오일러 투어 테크닉을 적용하면 쉽게 할 수 있다. 앞에서 나온 트리에 오일러 투어 테크닉을 적용해서 정점 번호를 다시 매기면 아래와 같다.

이제 세그먼트 트리로 그룹을 한번에 처리할 수 있다. 구현을 통해서 조금 더 자세히 알아보자.

 

첫 번째 DFS에서는 정점마다 서브트리의 크기를 구한다.

int sz[100005];
vector<int>e[100005];
void dfs1(int p, int u)
{
    sz[u] = 1;
    for(auto &v: e[u])
    {
        if(p == v)continue;
        dfs1(u, v);
        sz[u] += sz[v];
    }
}

다음으로 간선을 정렬한다.

int C(int a, int b){return sz[a] > sz[b];}

for(int i = 1; i <= n; i++)sort(e[i].begin(), e[i].end(), C);

두 번째 DFS는 오일러 투어 테크닉을 적용해서 그룹을 구하는 과정이다. 정점 번호 $u$와 오일러 투어 테크닉으로 다시 매겨진 번호 $E_u$(코드에서는 $et[u]$로 표현됨)가 각각 어디에 들어가는지 주의하면서 보도록 하자.

int c, g, d[100005], et[100005], gr[100005], gx[100005], pv[100005];
void dfs2(int u, int k, int r)
{
    et[u] = ++c;
    d[c] = k; // 정점 u의 깊이는 d[et[u]]가 된다.
    pv[c] = r; // v의 부모 정점이 u일 때 pv[et[v]] = et[u]가 된다.
    if(d[c - 1] >= d[c])gx[++g] = c; // d[c - 1] >= d[c]인 경우 두 정점은 부모 - 자식 관계가 아니므로 새로운 그룹을 만들어야 한다. gx[g]는 g번 그룹에서 가장 깊이가 얕은 정점이다.
    gr[c] = g; // 정점 u의 그룹 번호는 gr[et[u]]이다.
    for(auto &v: e[u])
    {
        if(sz[v] < sz[u])dfs2(v, k + 1, et[u]); // sz[v] < sz[u]인 경우 v는 u의 자식이다. 이 부분에서는 et[u] 대신 c를 쓸 수 없다.
    }
}

이제 전처리는 다 되었고, 세그먼트 트리를 이용해서 그룹을 한번에 처리하는 방법을 알아보자. 세그먼트 트리의 기본적인 사용법은 세그먼트 트리를 소개할 때 다루었으므로 여기서 또 깊게 다루지는 않는다. 먼저 정점을 처리하는 경우, ($x$와 $y$가 경로의 양 끝 정점이고, 경로에 존재하는 정점에 할당된 값들 중 최댓값을 구하는 상황이라고 하자)

int f(int x, int y)
{
    int m = 0;
    x = et[x];
    y = et[y];
    while(gr[x] != gr[y])
    {
        int cx = gx[gr[x]], cy = gx[gr[y]]; // cx와 cy는 그룹에서 루트와 가장 가까운 정점
        if(d[cx] > d[cy]) // 더 깊은 곳에 있는 그룹을 먼저 처리함
        {
            m = max(m, getMax(cx, x, 1));
            x = pv[cx];
        }
        else
        {
            m = max(m, getMax(cy, y, 1));
            y = pv[cy];
        }
        m = max(m, getMax(min(x, y), max(x, y), 1)); // x와 y가 같은 그룹에 속하게 되었다면 둘 중 하나는 경로의 양 끝 정점의 LCA가 된다.
    }
    return m;
}

이런 식으로 구현할 수 있다. $getMax$ 함수는 세그먼트 트리를 소개하는 글에 나온 $getSum$ 함수와 비슷한 방식으로 작동하는 것으로 이해하면 된다. (최소 깊이가) 더 깊은 그룹부터 처리하면서 루트 쪽으로 올라가는 방식에 유의하자.

 

간선을 처리하는 경우는 약간 더 복잡하다. 먼저 각 간선에 번호를 매겨야 세그먼트 트리로 처리할 수 있는데, 간선이 항상 부모와 자식을 연결하고, 그중 자식 쪽은 모두 다르기 때문에 이걸 간선 번호로 하면 거의 비슷한 방식으로 처리할 수 있다. 한 가지 주의할 점이라면 마지막 부분이 다음과 같이 바뀐다는 것 정도가 있다.

m = max(m, getMax(min(x, y) + 1, max(x, y), 1)); // LCA를 빼고 계산해야 함

전체 코드는 다음과 같다. 세그먼트 트리 코드까지 다 있어서 조금 길다.

#import<bits/stdc++.h>
using namespace std;
int c, g, d[100005], et[100005], gr[100005], gx[100005], pv[100005], sz[100005];
int a[1 << 18], l[1 << 18], r[1 << 18];
vector<int>e[100005];
int C(int a, int b){return sz[a] > sz[b];}
void dfs1(int p, int u)
{
    sz[u] = 1;
    for(auto &v: e[u])
    {
        if(p == v)continue;
        dfs1(u, v);
        sz[u] += sz[v];
    }
}
void dfs2(int u, int k, int r)
{
    et[u] = ++c;
    d[c] = k;
    pv[c] = r;
    if(d[c - 1] >= d[c])gx[++g] = c;
    gr[c] = g;
    for(auto &v: e[u])
    {
        if(sz[v] < sz[u])dfs2(v, k + 1, et[u]);
    }
}
void REP(int i, int v)
{
    i = p + et[i];
    for(a[i] = v; i >>= 1;)a[i] = a[i << 1] + a[i << 1 | 1];
}
int getMax(int x, int y, int d)
{
    if(x <= l[d] && r[d] <= y)return a[d];
    if(x > r[d] || y < l[d])return 0;
    return max(getMax(x, y, d << 1), getMax(x, y, d << 1 | 1));
}
int f(int x, int y)
{
    int m = 0;
    x = et[x];
    y = et[y];
    while(gr[x] != gr[y])
    {
        int cx = gx[gr[x]], cy = gx[gr[y]];
        if(d[cx] > d[cy])
        {
            m = max(m, getMax(cx, x, 1));
            x = pv[cx];
        }
        else
        {
            m = max(m, getMax(cy, y, 1));
            y = pv[cy];
        }
        m = max(m, getMax(min(x, y), max(x, y), 1));
    }
    return m;
}
int main()
{
    int n, x, y;
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    
    dfs1(0, 1);
    for(int i = 1; i <= n; i++)sort(e[i].begin(), e[i].end(), C);
    dfs2(1, 0, 0);
    
    int p = 1 << 17;
    for(int i = 0; i < p; i++)l[p + i] = r[p + i] = i;
    for(int i = p; --i;)
    {
        l[i] = l[i << 1];
        r[i] = r[i << 1 | 1];
    }
    for(int i = 1; i <= n; i++)cin >> a[p + et[i]];
    for(int i = p; --i;)a[i] = max(a[i << 1], a[i << 1 | 1]);
}

 

[연습문제]

 

BOJ 13510. 트리와 쿼리 1 (Platinum I)

세그먼트 트리로 간선 그룹을 관리하면 된다.

 

BOJ 13512. 트리와 쿼리 3 (Platinum I)

13510번과 비슷하다. 다만 13510번이 간선을 관리한다면 이 문제는 정점을 관리하고, 경로에서 조건을 만족하는 첫 번째 정점을 찾아야 하므로 약간 더 섬세한 처리가 필요하다.

 

→ solved.ac tag: hld

---

1. 다른 자료들과 대조하면 Heavy Edge와 Light Edge의 정의는 서로 약간씩 다를 수 있으나 개념을 이해하는 데는 지장이 없을 것이다. [본문으로]