HLD

트리의 경로에 관한 질의를 빠르게 처리할 수 있게 해주는, Heavy-Light Decomposition (HLD)에 대해 알아봅시다.

 

이전에 트리의 모든 서브트리를 하나의 구간으로 나타내게 해주는 Euler tour technique에 대한 글을 쓴 적이 있습니다.

https://anz1217.tistory.com/41 

Euler tour technique

이와 비슷하게 트리의 모든 경로도 HLD를 이용하면 몇 개의 구간으로 나눌 수 있고, 세그먼트 트리등의 자료구조를 사용할 수 있게 됩니다.

 

임의의 경로를 몇 개의 구간으로 나누기 위해서, 트리를 몇 개의 "체인"으로 분해해 봅시다.

트리의 루트에서 시작해 리프 노드를 만날 때까지 임의의 자식으로 탐색하는 것을 반복해서, 하나의 "체인"을 만들 수 있습니다.. 그리고 체인에 속하지 못한 정점 중 가장 루트와 가까운 것을 새로운 루트로 잡고, 이를 모든 정점이 하나의 체인에 포함될 때 까지 반복하면 됩니다.

 

예를 들어 다음과 같은 트리는,

다음과 같이 6개의 "체인"으로 분해할 수 있습니다.

일단 트리를 여러개의 체인으로 분해했다면, 일단 임의의 경로를 몇 개의 체인으로 나타낼 수 있습니다.

예를 들어, 위의 방식으로 분해한 트리에서 "6번 정점에서 8번 정점으로 가는 단순 경로"는,

(파란색 [6] 체인에서 구간 [6]), (빨간색 [1,2,5] 체인에서 구간 [1,2]), (주황색 [3,8] 체인에서 구간 [3,8]) 총 3개의 구간으로 경로를 나타낼 수 있게 됩니다.

 

여기에서 문제는, 이런식으로 임의로 체인을 만들면 어떤 경로를 나타내는데 너무 많은 체인이 사용될 수 있다는 것입니다.

 

예를 들어서 아래 그림과 같은 트리를,

이렇게 모든 체인이 2개의 정점만을 포함하도록 분해 한다면, 임의의 경로를 나타내는데 평균적으로 그 경로에 포함된 정점의 개수 만큼의 체인이 필요하게 되고, 이런 분해를 하는 의미가 없어집니다.

 

그러면 이를 어떻게 최적화 할 수 있을까요?

위의 방식으로 체인을 만들어 갈 때, 자식들 중 서브트리의 크기가 가장 큰 노드를 선택하면 됩니다.

이러한 방식으로 분해한 다음 루트에서부터 임의의 노드까지의 경로를 생각해 봅시다.

루트에서 시작하는 체인이 아니라 새로운 체인을 추가로 써야 된다면, 고려해야 하는 정점의 개수가 절반 이하로 줄어들게 됩니다. 따라서, 트리의 정점이 \(N\)개라면 어떤 경로라도 \(O(\log N)\)개의 체인만을 이용해 나타낼 수 있게 됩니다.

 

구현은 어떻게 할까요? ETT때 했던 것과 같이, 트리를 DFS로 탐색하면서 각 정점에 번호를 붙여주면 됩니다.

단, ETT는 DFS를 하는 중 각 정점의 자식들 중 어떤 것을 먼저 탐색하든지 아무 상관없었지만, 이번에는 각 자식을 루트로 하는 서브트리의 크기가 가장 큰 것 부터 탐색하면 됩니다. 각 정점에서 처음 탐색되는 자식은 자기 자신과 같은 체인에 속하고, 나머지 자식들은 새로운 체인의 루트임을 뜻합니다.

따라서, 1번 정점이 루트인 이 트리를 HLD 분해하면 다음과 같이 됩니다.

https://www.acmicpc.net/problem/13510

13510번: 트리와 쿼리 1

트리를 HLD 분해하고, 각 간선의 비용을 세그트리로 관리하여 1번 쿼리는 \(O(\log N)\), 2번 쿼리는 \(O(\log^2 N)\)에 처리할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cpdb;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int N = 100001;
 
int n, m;
vector <pii> graph[N];
pii edge[N];
 
int segTree[N * 4];
void update(int ptr, int l, int r, int i, int val)
{
    if (i < l || r < i) return;
    if (l == r)
    {
        segTree[ptr] = val;
        return;
    }
 
    update(ptr * 2, l, (l + r) / 2, i, val);
    update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, val);
 
    segTree[ptr] = max(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
 
int getVal(int ptr, int l, int r, int i, int j)
{
    if (j < l || r < i) return 0;
    if (i <= l && r <= j) return segTree[ptr];
 
    return max(getVal(ptr * 2, l, (l + r) / 2, i, j),
        getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j));
}
 
int sz[N];
int HLD_num[N];
int chain_lv[N];
int chain_head[N];
int chain_par[N];
 
void getSize(int v, int p)
{
    sz[v] = 1;
    for (auto& nxt : graph[v])
    {
        int nv = nxt.first;
        if (nv == p) continue;
 
        getSize(nv, v);
        sz[v] += sz[nv];
 
        // 서브트리 크기가 가장 큰 자식이 가장 먼저 방문되도록
        if (sz[nv] > sz[graph[v].front().first] || graph[v][0].first == p)
            swap(graph[v].front(), nxt);
    }
}
 
int HLD_cnt = 1;
void DFS(int v, int p, int l)
{
    HLD_num[v] = HLD_cnt++;
    chain_lv[v] = l;
 
    bool isFirst = true; // 현재 자식이 가장 먼저 방문되는 자식인지 (같은 체인인지)
    for (auto nxt : graph[v])
    {
        int nv = nxt.first;
        int w = nxt.second;
        if (nv == p) continue;
 
        if (isFirst)
        {
            chain_head[nv] = chain_head[v];
            chain_par[nv] = chain_par[v];
            DFS(nv, v, l);
            isFirst = false;
        }
        else
        {
            chain_head[nv] = nv;
            chain_par[nv] = v;
            DFS(nv, v, l + 1);
        }
 
        update(1, 1, n, HLD_num[nv], w);
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        graph[u].push_back({ v,w });
        graph[v].push_back({ u,w });
 
        edge[i] = { u,v };
    }
 
    getSize(1, 0); // 서브트리 크기
 
    chain_head[1] = 1;
    DFS(1, 0, 1); // HLD
 
    cin >> m;
    while (m--)
    {
        int o; cin >> o;
        if (o == 1)
        {
            int i, c; cin >> i >> c;
            int& u = edge[i].first;
            int& v = edge[i].second;
            if (HLD_num[u] > HLD_num[v]) swap(u, v);
 
            update(1, 1, n, HLD_num[v], c);
        }
        else
        {
            int u, v; cin >> u >> v;
            if (chain_lv[u] > chain_lv[v]) swap(u, v);
 
            int ans = 0;
            while (chain_lv[u] < chain_lv[v])
            {
                ans = max(ans, getVal(1, 1, n, HLD_num[chain_head[v]], HLD_num[v]));
                v = chain_par[v];
            }
 
            while (chain_head[u] != chain_head[v])
            {
                ans = max(ans, getVal(1, 1, n, HLD_num[chain_head[u]], HLD_num[u]));
                ans = max(ans, getVal(1, 1, n, HLD_num[chain_head[v]], HLD_num[v]));
                u = chain_par[u];
                v = chain_par[v];
            }
 
            if (HLD_num[u] > HLD_num[v]) swap(u, v);
            ans = max(ans, getVal(1, 1, n, HLD_num[u] + 1, HLD_num[v]));
 
            cout << ans << '\n';
        }
    }
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

+ 요즘 많이 가입 신청이 들어오고 있습니다만, 꼭 그룹에 가입하셔서 제 문제들을 푸실 필요는 없습니다.

solved.ac 에서 태그를 찾아 푸시거나 백준 단계별로 풀기 에서 문제를 찾아 푸셔도 충분합니다!

그룹은 단순히 제 개인용 알고리즘 문제집 정리 용도이니 참고해주세요!

https://www.acmicpc.net/group/7712

ANZ1217