Heavy Light Decomposition

Heavy Light Decomposition 은 트리에서 segment tree 등의 자료 구조를 활용할 수 있도록 만드는 방법이다.

1차원에서 업데이트, 쿼리를 처리하는 문제는 segment tree 등의 자료구조를 활용하여 풀 수 있다. 하지만 트리에서는 이 과정이 어렵기 때문에 트리를 몇개의 체인으로 쪼갠 후 각 체인에서 segment tree 등을 사용하는 것이다.

하지만 만약 이 체인의 수가 많아지면 그만큼 시간이 많이 걸리기 때문에 체인의 개수를 적당히 적게 만드는 방법이 필요하다.

 

 

HLD 는 다음과 같이 트리에서 각 노드에서 자식들 중 가장 서브트리가 큰 서브트리까지의 간선을 "무거운 간선"으로 분류한다.이렇게 해서 "무거운 간선"들로만 묶이면 체인들 몇개로 트리가 분해되게 된다.

 

이때 가장 중요한 점은 어떤 두 점을 잡았을 때 그 두 점사이의 경로는 최대 $logN$ 개의 체인을 지난다는 것이다. 일단 u-v를 u-LCA, LCA-v 로 쪼갠다. 체인이 한번 바뀌려면 자식들의 서브트리의 크기가 항상 반 이하로 떨어진다는 것을 의미한다. 반 이상이라 가정하자. 이 정점이 "무거운 정점" 이 아니기 때문에 무거운 정점은 이 반 이상인 점보다 커야 하고, 이는 모순이다. 즉, 한번 체인이 바뀔 때마다 개수가 반씩 줄어들고, 따라서 체인은 최대 $logN$ 개 존재한다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int NEGINF = -987654321;

struct Edge { int u, v; };

int N, Q;
vector<pii> adj[MAXN+10];
Edge edge[MAXN+10];

int sz[MAXN+10], dep[MAXN+10], par[MAXN+10], weight[MAXN+10], head[MAXN+10], idx[MAXN+10], cnt=1;

struct SEG
{
    int tree[4*MAXN+10];
    SEG() { memset(tree, 0, sizeof(tree)); }

    void update(int node, int tl, int tr, int pos, int val)
    {
        if(pos<tl || tr<pos) return;
        if(tl==tr)
        {
            tree[node]=val;
            return;
        }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, pos, val);
        update(node*2+1, mid+1, tr, pos, val);
        tree[node]=max(tree[node*2], tree[node*2+1]);
    }

    int query(int node, int tl, int tr, int l, int r)
    {
        if(r<tl || tr<l) return NEGINF;
        if(l<=tl && tr<=r) return tree[node];
        int mid=tl+tr>>1;
        return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
    }
};
SEG seg;

void dfs(int now, int bef, int depth)
{
    sz[now]=1;
    dep[now]=depth;
    par[now]=bef;
    for(auto nxt : adj[now]) if(nxt.first!=bef)
    {
        dfs(nxt.first, now, depth+1);
        sz[now]+=sz[nxt.first];
        weight[nxt.first]=nxt.second;
    }
}

void hld(int now, int bef)
{
    idx[now]=cnt++;
    int heavy=0;
    for(auto nxt : adj[now]) if(nxt.first!=bef && sz[heavy]<sz[nxt.first]) heavy=nxt.first;

    if(!heavy) return;
    head[heavy]=head[now];
    hld(heavy, now);

    for(auto nxt : adj[now]) if(nxt.first!=bef && nxt.first!=heavy)
    {
        head[nxt.first]=nxt.first;
        hld(nxt.first, now);
    }
}

int query(int u, int v)
{
    int ans=NEGINF;
    while(head[u]!=head[v])
    {
        if(dep[head[u]]>dep[head[v]]) swap(u, v);
        ans=max(ans, seg.query(1, 1, N, idx[head[v]], idx[v]));
        v=par[head[v]];
    }
    if(u==v) return ans;
    if(dep[u]>dep[v]) swap(u, v);
    ans=max(ans, seg.query(1, 1, N, idx[u]+1, idx[v]));
    return ans;
}

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<N; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edge[i]={u, v};
    }

    dfs(1, 0, 1);
    head[1]=1;
    hld(1, 0);

    for(i=1; i<N; i++)
    {
        if(par[edge[i].u]==edge[i].v) swap(edge[i].u, edge[i].v);
        seg.update(1, 1, N, idx[edge[i].v], weight[edge[i].v]);
    }

    scanf("%d", &Q);
    while(Q--)
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if(t==1)
        {
            weight[edge[a].v]=b;
            seg.update(1, 1, N, idx[edge[a].v], weight[edge[a].v]);
        }
        else
        {
            printf("%d\n", query(a, b));
        }
    }
}

 

1. HLD 구성

 

1. DFS

먼저, 각 정점에서의 서브트리의 크기, 각 정점의 부모, 각 정점의 깊이를 구한다.

 

2. HLD

이제 구한 서브트리의 크기를 바탕으로 각 정점에서 무거운 간선을 하나씩 골라서, 각 정점마다 체인의 head 를 구해준다.

만약 그 정점이 무거운 정점이라면 head[heavy]=head[now] 가 되고, 아닐 시 각각 체인의 시작이 되어 head[nxt]=nxt 가 된다.

주의해야 할 점은 1번 정점은 미리 head[1]=1 을 선언하고 시작해야 한다.

또한, 그 도중 각각의 DFS 방문순서를 모두 알아야 한다. 이는 하나의 segment tree를 통해 전체 체인들을 처리할 수 있도록 해준다. 뿐만 아니라, 이를 이용하면 서브트리에 대한 업데이트를 lazy propagation 을 이용하여 처리할 수도 있기도 하다.

 

2. update

segment tree 에 idx[u]에 update 해 준다.

 

3. query

u, v가 다른 체인에 위치할 때까지 계속 더 깊은 노드를 한단계씩 올리며, 답을 갱신해 준다.

여기서 query가 노드에 대한 것일수도, 간선에 대한 것일 수도 있다. 

이것을 머리 아프지 않게 해결할 수 있는 방법은, 1번 노드에 위에 꼭지 간선을 하나 달아주는 것이다.

그러면 간선도 N개, 각 노드의 부모를 잇는 간선과 일대일대응한다.