Centroid Decomposition

작성일 | In

서론

센트로이드는 트리에서 분할정복을 할 수 있도록 도와주는 도구입니다.

수열에서 문제를 풀다보면 아래와 같은 과정을 통해 분할 정복을 할 때가 있습니다.

  1. 수열의 중간 지점인 $m = \lfloor\frac{s+e}{2}\rfloor$을 잡는다.
  2. $m$을 포함하는 모든 구간을 고려한다.
  3. $m$이 포함되는 구간은 모두 고려했으니, $m$ 기준으로 양쪽으로 자른 수열에 대해 재귀적으로 수행한다.

수열의 모든 구간을 Naive하게 본다면 $O(N^2)$이 걸리지만, 어떤 원소 하나를 포함하는 모든 구간을 $O(N)$이나 $O(N \log N)$만에 확인할 수 있다면 위 분할 정복 과정을 통해 각각 $O(N \log N)$, $O(N \log^2 N)$에 문제를 풀 수 있습니다. 매번 수열의 크기가 절반 이상 줄어들기 때문에 log 시간이 보장됩니다.

수열에서는 단순히 중간 지점을 잡으면 되기 때문에 쪼개지는 조각들의 크기를 $N/2$ 이하로 줄이는 것이 쉽습니다. 트리에서도 분할 정복을 하고 싶은데 어떤 정점을 잡아서 쪼개야 할까요?

센트로이드는 이 궁금증을 풀어줍니다.

트리의 센트로이드

우리의 목표는 정점 하나를 지웠을 때 쪼개지는 서브트리들의 크기가 모두 절반 이하가 되도록 하는 정점을 찾는 것입니다. 다시 말해, 정점 v를 지웠을 때 쪼개지는 서브트리들의 크기의 최댓값을 $maxsize(v)$라고 한다면, $maxsize(v) \leq N/2$인 정점을 찾는 것입니다.
그리고 이런 정점을 트리의 센트로이드(Centroid)라고 합니다.

모든 트리에서 이러한 센트로이드는 항상 존재합니다. 귀류법을 사용하여 증명합니다.

센트로이드가 없는 크기 $N$짜리 트리 $T$가 있다고 합시다.
$T$에서 $maxsize(v)$가 최소인 정점을 $x$라고 합시다. 위 가정에 의해서 $x$를 제거했을 때 쪼개지는 가장 큰 서브트리 $T_1$의 크기는 $N/2$보다 큽니다.
$T_1$에서 $x$와 인접한 정점을 $y$라고 하면, $maxsize(x) > maxsize(y)$이므로 모순이 생깁니다.

이 증명 과정을 통해 현재 정점을 제거했을 때 쪼개지는 서브 트리의 크기가 $N/2$ 초과인 것이 있다면, 그 서브 트리 안에 센트로이드가 있다는 것을 알 수 있습니다. 따라서 센트로이드를 찾는 방법은 다음과 같습니다.

  1. 임의의 정점 $v$을 루트로 잡고 DFS를 돌린다. 동시에 각 서브 트리의 크기를 구한다.
  2. $v$ 아래에 달려있는 서브 트리 중 크기가 $N/2$ 초과인 것이 있다면 그 방향으로 한 칸 내려간다.

센트로이드를 찾는 것은 아래 코드처럼 구현하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
int sz[101010]; // 서브 트리의 크기
vector<int> g[101010]; // 인접 리스트
int getSize(int v, int b = -1){ // 서브 트리의 크기를 구하는 DFS
    sz[v] = 1;
    for(auto i : g[v]) if(i != b) sz[v] += getSize(i, v);
    return sz[v];
}
int getCent(int v, int b = -1, int cap = n){ // 센트로이드를 찾는 DFS
    for(auto i : g[v]) if(&& i != b && sz[i]*2 > cap) return getCent(i, v, cap);
    return v;
}

트리에서의 분할 정복

모든 서브 트리의 크기를 절반 이하로 줄어줄 방법을 찾았으니, 분할 정복을 어떻게 하는지 알아봅시다.

수열에서는 중간 지점을 잡아서 중간 지점을 지나는 모든 구간을 봐줬습니다. 비슷하게, 트리에서는 센트로이드를 잡아서 센트로이드를 지나는 모든 경로를 봐줍니다. 당연히 $O(N^2)$보다는 빠르게 해야합니다. $O(N^2)$이면 굳이 분할 정복할 필요 없이 Naive하게 봐줘도 되기 때문이죠…

BOJ 5820 경주(IOI’11 Day1 #2)를 봅시다. 길이가 정확히 $K$인 경로를 찾아야 하는데, 그런 경로가 여러 개 존재한다면 간선의 개수가 가장 적은 경로를 찾아야 합니다. 경로를 구성하는 간선의 개수만 구해주면 됩니다.

분할 정복을 할 것이므로 트리의 센트로이드 $c$를 지나면서 길이가 $K$인 경로만 생각해주면 됩니다. $c$를 지나면서 길이가 $K$인 경로들을 모두 보는 것은 아래 과정대로 하면 됩니다.

  1. 각 서브 트리마다 길이가 $x$인 최소 깊이를 전처리
  2. 다른 서브 트리에서 $c$와 $K-x$만큼 떨어진 정점이 있다면 (현재 정점의 깊이) + ($c$와 거리가 $K-x$인 정점의 최소 깊이)로 정답 갱신

위 과정은 $O(N)$에 할 수 있으므로, 전체 문제는 $O(N \log N)$에 풀 수 있습니다.

센트로이드 트리

센트로이드 트리는 센트로이드 디컴포지션 과정을 이쁘게 표현한 구조입니다. 트리에서 재귀적으로 센트로이드를 찾은 뒤, 새로 생성한 트리입니다.

원본 트리의 센트로이드는 빨간색 정점입니다. 빨간색 정점을 제거해서 쪼개지는 서브 트리들에서 다시 한 번 센트로이드를 찾은 것이 주황색 정점, 다시 한 번 센트로이드를 찾은 것이 노란색, 그 다음이 초록색입니다.
이런 트리의 센트로이드 트리는 아래와 같습니다.

센트로이드 트리는 몇 가지 성질이 있습니다.

  1. 센트로이드 트리의 높이는 당연히 $O(\log N)$ 이하입니다.
  2. 원본 트리에서 정점 $u$에서 $v$로 가는 경로는 센트로이드에서의 $LCA(u, v)$에 의해 2개로 분할됩니다. 다시 말해 $l = LCA(u, v)$라고 하면, 원본 트리에서 $u, v$를 잇는 경로는 $u, l$를 잇는 경로와 $l, v$를 잇는 경로로 쪼갤 수 있습니다.
  3. 센트로이드 트리 상에서 $v$의 조상들을 $P_1, P_2, … , P_k$라고 합시다. 2번 성질에 의해 $v$와 다른 정점을 잇는 모든 경로는 $P_1$을 지나는 경로, $P_2$를 지나는 경로, … , $P_k$를 지나는 경로로 구분해서 볼 수 있습니다.

센트로이드 트리의 성질을 활용하는 대표적인 문제인 BOJ 13514 트리와 쿼리 5를 봅시다.

set을 $N$개 관리할 건데, $i$번째 set에서는 센트로이드 상에서 루트와 $i$번 정점을 잇는 경로에 있는 흰색 정점과 $i$번 정점의 거리를 저장합니다. 센트로이드 트리의 높이는 $O(\log N)$이기 때문에 각 set에는 최대 $O(\log N)$개의 정점이 들어갑니다.

$N$개의 set을 다 만들었다면 쿼리를 처리하는 것은 간단합니다.
트리에서 임의의 정점 $u$와 $v$를 잇는 경로는 센트로이드 트리 상에서 $u$와 $v$의 lca를 기준으로 나눌 수 있습니다. 그러므로 센트로이드 트리에서의 $v$의 선조를 모두 살펴보면 $v$와 다른 노드 사이의 모든 경로의 정보를 알 수 있습니다.

연습 문제