개요

트리 체인 분할은 트리를 여러 체인으로 나누어 선형 자료구조를 활용할 수 있도록 하는 기법이다. 이 중 가장 널리 사용되는 방식은 Heavy-Light Decomposition(HLD)이다.

다음과 같은 개념들을 정의한다:

• 무거운 자식: 특정 노드의 모든 자식 중 서브트리 크기가 가장 큰 자식
• 가벼운 자식: 무거운 자식을 제외한 나머지 자식들
• 무거운 간선: 부모와 무거운 자식을 연결하는 간선
• 가벼운 간선: 부모와 가벼운 자식을 연결하는 간선

구현 방법

HLD는 두 번의 DFS를 통해 구현된다. 첫 번째 DFS에서는 각 노드의 깊이, 부모, 서브트리 크기, 무거운 자식을 계산한다. 두 번째 DFS에서는 각 체인의 시작점(헤드)를 설정한다.

void preprocess(int node, int parent, int level) {
    depth[node] = level;
    father[node] = parent;
    subtree_size[node] = 1;
    int max_child_size = 0;
    
    for(int child : adjacency[node]) {
        if(child != parent) {
            preprocess(child, node, level + 1);
            subtree_size[node] += subtree_size[child];
            
            if(subtree_size[child] > max_child_size) {
                heavy_child[node] = child;
                max_child_size = subtree_size[child];
            }
        }
    }
}

void decompose(int node, int chain_head) {
    chain_top[node] = chain_head;
    position_in_array[node] = ++timer;
    
    if(heavy_child[node] != -1) {
        decompose(heavy_child[node], chain_head);
    }
    
    for(int child : adjacency[node]) {
        if(child != father[node] && child != heavy_child[node]) {
            decompose(child, child);
        }
    }
}

특성

HLD의 핵심 특성은 임의의 노드에서 루트까지 경로상에 있는 가벼운 간선의 개수가 O(log n)이라는 것이다. 이를 통해 트리 상의 경로 쿼리를 효율적으로 처리할 수 있다.

LCA 구하기

HLD를 이용해 두 노드의 최소 공통 조상(LCA)을 구할 수 있다. 두 노드가 서로 다른 체인에 속해 있다면, 더 깊은 체인의 헤드를 위로 올려 같은 체인에 도달할 때까지 반복한다.

int find_lca(int u, int v) {
    while(chain_top[u] != chain_top[v]) {
        if(depth[chain_top[u]] > depth[chain_top[v]]) {
            u = father[chain_top[u]];
        } else {
            v = father[chain_top[v]];
        }
    }
    return (depth[u] < depth[v]) ? u : v;
}

세그먼트 트리와의 결합

HLD와 세그먼트 트리를 결합하면 트리 상의 경로 쿼리와 업데이트를 효율적으로 처리할 수 있다. 노드들의 값을 배열에 매핑하고, 해당 배열을 기반으로 세그먼트 트리를 구성한다.

// 경로 업데이트 함수
void update_path(int x, int y, int value) {
    while(chain_top[x] != chain_top[y]) {
        if(depth[chain_top[x]] > depth[chain_top[y]]) {
            segment_update(1, n, position_in_array[chain_top[x]], position_in_array[x], 1, value);
            x = father[chain_top[x]];
        } else {
            segment_update(1, n, position_in_array[chain_top[y]], position_in_array[y], 1, value);
            y = father[chain_top[y]];
        }
    }
    
    if(depth[x] > depth[y]) {
        segment_update(1, n, position_in_array[y], position_in_array[x], 1, value);
    } else {
        segment_update(1, n, position_in_array[x], position_in_array[y], 1, value);
    }
}

// 서브트리 업데이트 함수
void update_subtree(int node, int value) {
    segment_update(1, n, position_in_array[node], position_in_array[node] + subtree_size[node] - 1, 1, value);
}

간선 가중치 처리

트리의 간선에 가중치가 주어지는 경우, 간선 가중치를 점 가중치로 변환하여 처리할 수 있다. 각 노드의 가중치를 부모와의 간선 가중치로 정의하면 된다.

void convert_edge_weights() {
    for(int i = 2; i <= n; i++) {
        node_weight[i] = edge_weight[parent[i]][i];
    }
}

경로 쿼리를 수행할 때는 두 노드가 같은 체인에 속해 있을 경우, 깊이가 더 낮은 노드의 다음 위치부터 시작해야 한다.