중심 분해 (Centroid Decomposition)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 4분 · 1,282자/단어 #algorithm #tree #centroid #centroid-decomposition

정의

중심 분해 (Centroid Decomposition) 는 트리를 중심 으로 재귀적으로 분할하여 O(log N) 깊이의 분해 트리 를 만드는 기법. 각 레벨에서 트리 크기가 절반 이하로 줄어 총 깊이 O(log N), 전체 정점 방문 횟수 O(N log N).

핵심 응용: 트리 경로 쿼리 (거리 k 이하 정점 쌍 개수, 경로 가중치 합 등) 를 O(N log N) 전처리 + O(log N) 쿼리로 해결.

문제 상황과 동기

“거리 k 이하인 정점 쌍 개수” 같은 쿼리:

naive: 모든 쌍 O(N^2) 탐색 → N=10^5 면 불가능.
centroid decomposition: 각 centroid 를 중심으로 경로를 O(N log N) 에 전처리 → 쿼리 O(log N).

핵심 통찰: 모든 경로는 어떤 centroid 를 “최고 조상” 으로 하는 분해 트리 상에서 유일하게 분류. 경로 (u, v) 는 분해 트리에서 lca(u, v) 인 centroid 를 정확히 한 번 지남.

PS / 실무 위치: BOJ 백준 플래티넘+ 문제 (트리 쿼리), 네트워크 분석 (중심 노드 계층).

시각화

핵심 아이디어

invariant:

분해 트리 깊이 = O(log N). 매 레벨에서 서브트리 크기 절반 이하.
모든 정점은 O(log N) 번 방문. 각 분해 레벨에서 한 번씩.
경로 (u, v) 는 분해 트리 상 lca(u, v) 에서 정확히 한 번 처리.

알고리즘 흐름:

centroid_decompose(T):
    c = find_centroid(T)
    mark c as removed
    for each component C after removing c:
        centroid_decompose(C)
    build_queries_on(c)   # c 를 경유하는 모든 경로 처리

알고리즘

decompose(u):
    tree_size = dfs_size(u, -1)
    c = find_centroid(u, -1, tree_size)
    removed[c] = true
    
    process_centroid(c)   # c 를 루트로 한 경로 쿼리 처리
    
    for v in adj[c]:
        if not removed[v]:
            decompose(v)

process_centroid(c):
    # c 를 경유하는 모든 경로에 대한 전처리
    # 예: 거리 배열, 카운팅, 서브트리별 분리 집계

구현

// Centroid Decomposition: O(N log N) 구축
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005];
int sz[100005], par[100005];
bool removed[100005];

int dfs_size(int u, int p) {
  sz[u] = 1;
  for (int v : adj[u]) {
      if (v == p || removed[v]) continue;
      sz[u] += dfs_size(v, u);
  }
  return sz[u];
}

int find_centroid(int u, int p, int tree_size) {
  for (int v : adj[u]) {
      if (v == p || removed[v]) continue;
      if (sz[v] > tree_size / 2)
          return find_centroid(v, u, tree_size);
  }
  return u;
}

void decompose(int u, int p = -1) {
  int tree_size = dfs_size(u, -1);
  int c = find_centroid(u, -1, tree_size);
  removed[c] = true;
  par[c] = p;
  
  // process_centroid(c) 여기서 쿼리 처리
  
  for (int v : adj[c]) {
      if (!removed[v])
          decompose(v, c);
  }
}

int main() {
  int n; cin >> n;
  for (int i = 0; i < n - 1; i++) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  
  decompose(1);
  
  cout << "Decomposition complete.\n";
  for (int i = 1; i <= n; i++)
      cout << "par[" << i << "] = " << par[i] << "\n";
}

# Centroid Decomposition
import sys
sys.setrecursionlimit(300000)

N = int(input())
adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
  u, v = map(int, input().split())
  adj[u].append(v)
  adj[v].append(u)

sz = [0] * (N + 1)
par = [-1] * (N + 1)
removed = [False] * (N + 1)

def dfs_size(u, p):
  sz[u] = 1
  for v in adj[u]:
      if v == p or removed[v]:
          continue
      sz[u] += dfs_size(v, u)
  return sz[u]

def find_centroid(u, p, tree_size):
  for v in adj[u]:
      if v == p or removed[v]:
          continue
      if sz[v] > tree_size // 2:
          return find_centroid(v, u, tree_size)
  return u

def decompose(u, p=-1):
  tree_size = dfs_size(u, -1)
  c = find_centroid(u, -1, tree_size)
  removed[c] = True
  par[c] = p
  
  # process_centroid(c)
  
  for v in adj[c]:
      if not removed[v]:
          decompose(v, c)

decompose(1)
print("Decomposition complete.")
for i in range(1, N + 1):
  print(f"par[{i}] = {par[i]}")

// Java Centroid Decomposition
import java.util.*;
import java.io.*;

public class Main {
  static List<Integer>[] adj;
  static int[] sz, par;
  static boolean[] removed;
  static int N;
  
  static int dfsSize(int u, int p) {
      sz[u] = 1;
      for (int v : adj[u]) {
          if (v == p || removed[v]) continue;
          sz[u] += dfsSize(v, u);
      }
      return sz[u];
  }
  
  static int findCentroid(int u, int p, int treeSize) {
      for (int v : adj[u]) {
          if (v == p || removed[v]) continue;
          if (sz[v] > treeSize / 2)
              return findCentroid(v, u, treeSize);
      }
      return u;
  }
  
  static void decompose(int u, int p) {
      int treeSize = dfsSize(u, -1);
      int c = findCentroid(u, -1, treeSize);
      removed[c] = true;
      par[c] = p;
      
      // process_centroid(c)
      
      for (int v : adj[c]) {
          if (!removed[v])
              decompose(v, c);
      }
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      adj = new ArrayList[N + 1];
      for (int i = 0; i <= N; i++) adj[i] = new ArrayList<>();
      sz = new int[N + 1];
      par = new int[N + 1];
      removed = new boolean[N + 1];
      Arrays.fill(par, -1);
      
      for (int i = 0; i < N - 1; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj[u].add(v);
          adj[v].add(u);
      }
      
      decompose(1, -1);
      
      System.out.println("Decomposition complete.");
      for (int i = 1; i <= N; i++)
          System.out.println("par[" + i + "] = " + par[i]);
  }
}

stdin

결과

Decomposition complete.
par[1] = -1
par[2] = 1
par[3] = 1
par[4] = 2
par[5] = 2
par[6] = 3
par[7] = 3

복잡도

항목	값
전처리 (분해)	O(N log N)
공간	O(N)
쿼리 (분해 트리 높이)	O(log N)
분해 트리 깊이	O(log N)

응용 패턴

1. 거리 k 이하 정점 쌍 개수

각 centroid c 에서:

c 를 루트로 DFS, 모든 정점의 거리 계산.
서브트리별로 분리해서 카운팅 (한 서브트리 내 쌍은 제외).
두 서브트리 간 쌍만 집계.

시간 복잡도: O(N log N).

2. 동적 쿼리 (정점 색칠 + 최단 거리)

분해 트리 상에서 각 정점 u 는 “조상 centroid 들까지의 거리” 를 저장. 정점 색칠 시 조상들 갱신 → 쿼리 O(log N).

3. K번째 가까운 정점

분해 트리 + 우선순위 큐로 K번째 탐색.

변형

Weighted Centroid Decomposition

간선 가중치가 있는 트리에서도 동일. 거리 배열에 가중치 합을 저장.

Dynamic Centroid Decomposition

간선 추가/삭제는 어려움. 실전에서는 재분해 또는 Link/Cut Tree.

함정

1. removed 배열 누락

분해 도중 이미 제거된 centroid 를 다시 방문하면 무한 루프. removed[c] = true 필수.

2. par 배열 관리

분해 트리의 부모 par[c] 를 기록해야 쿼리 시 조상 순회 가능. 초기값 -1.

3. 서브트리 중복 카운팅

같은 서브트리 내 쌍을 두 번 세지 않도록 서브트리별 분리 집계 필요.

4. 0-indexed vs 1-indexed

트리 입력 형식 확인. adj, sz, par 배열 크기 주의.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 13159	배열	-	kokoa-lab
BOJ 5820	경주	-	kokoa-lab
BOJ 17429	국제 메시지	-	kokoa-lab
BOJ 12467	트리 색칠하기	-	kokoa-lab

참고

이 글의 용어 (4개)

최소 공통 조상 (Lowest Common Ancestor)algorithm: 정의 최소 공통 조상 (LCA, Lowest Common Ancestor) 는 트리에서 두 노드 u, v 의 공통 조상 중 가장 깊은 (루트에서 가장 먼) 노드. Binary L…
트리의 중심 (Centroid)algorithm: 정의 트리의 중심 (Centroid) 은 정점 v 를 제거했을 때 생기는 모든 connected component 의 크기가 ⌊N/2⌋ 이하가 되는 정점. 모든 트리는 최소 1개…
Graph DP: 트리/DAG 위 DPalgorithm: 정의 Graph DP 는 그래프 구조를 이용한 DP. 사이클 없는 그래프 (트리, DAG) 에서 특히 자연스러움. Tree DP 루트 트리에서 자식 서브트리 결과를 조합. Rer…
Heavy-Light Decompositionalgorithm: 정의 Heavy-Light Decomposition (HLD) 는 트리를 O(log N) 개의 경로 (chain) 로 분해해 임의 경로 쿼리 (u-v 경로의 합/최대/최소) 를 …