Centroid Decomposition - 센트로이드 분할

센트로이드 분할

1. 존재의의

센트로이드 분할 = 트리에서의 분할 정복 기법

트리에서 어떠한 문제( i.e.) 길이가 K인 경로의 개수를 구하라)를 해결해야 될 때
트리를 크기가 더 작은 서브 트리들로 분할하여 문제를 적용한다. 이때 효율적인 분할의 대표적인 기법이 센트로이드 분할이다.

2. 센트로이드란

트리의 무게중심인 정점.
트리를 어떤 정점을 기준으로 차수만큼의 서브트리들로 나눌 수 있다.

이때 모든 서브트리의 크기가 전체 트리 크기의 절반 이하일 때, 그 정점을 Centroid라 한다.

Q) 센트로이드는 항상 존재하는가?
A) 그렇다

증명 1) 센트로이드 탐색 알고리즘
임의의 노드를 고르자. 그 노드를 루트로 하는 트리를 생각한다.
모든 서브트리의 크기가 조건을 만족한다면 그 노드가 센트로이드다. 
조건을 만족하지 않는 서브트리가 있다면 그 서브트리의 루트에 위 알고리즘을 적용하여 재귀적으로 탐색한다.

증명 2) 귀류법
트리의 센트로이드가 존재하지 않는다고 하자.
노드 중 트리를 분할했을 때 서브트리의 크기의 최댓값이 최소가 되는 노드를 v라 하자. 
v에 연결된 노드 중 서브트리의 크기가 최대인 노드를 u라 하자.
마지막으로 전체 트리의 크기를 N이라 하자.

u를 루트로 하는 서브트리의 크기는 floor(N/2) 초과이다. 
이때 u를 기준으로 트리를 분할하면 u를 기준으로 부모 쪽으로 올라갔을 때 서브트리의 크기는 floor(N/2) 미만 이다. 
따라서 u를 루트로 하는 서브트리에서 u를 제외하면 노드의 개수가 ceil(N/2) 이상이 된다. 
트리의 센트로이드가 존재하지 않으며, 동시에 v의 정의를 만족시키는 u는 존재할 수 없으므로 트리의 센트로이드는 존재한다.

3. 센트로이드 분할 알고리즘의 구성

1. 트리 위의 임의의 노드를 고른다. O(1)
2. 고른 노드를 루트로하는 트리의 센트로이드를 구한다. O(N)
3. 센트로이드를 포함하는 어떤 집합( ex)경로) 에 대한 정답을 구한다. O(T) ( >= O(N) )
4. 센트로이드를 기준으로 트리를 서브트리들로 분할한 다음 2~4를 적용한다. 
분할의 단계 수는 O(log N)이므로 전체 시간복잡도는 O(T log N)이 된다.

4. 센트로이드 분할의 구현

간선에 가중치가 있는 트리다.

(0) 준비물

int siz[N];
bool vis[N];
vector<pii> g[N];
#define ok(x) x!=p && !vis[x]

vis 배열은 센트로이드를 기준으로 트리를 서브트리들로 분할하고 분할정복을 적용할 때
센트로이드를 탐색에서 배제하기 위한 체크 배열이다.

(1) 센트로이드를 찾기 위해 모든 서브트리의 크기를 구하는 코드

int get_siz(int v,int p=-1){
	siz[v] = 1;
	for(auto[nxt,w]:g[v]) if(ok(nxt))
		siz[v] += get_siz(nxt,v);
	return siz[v];
}

(2) 센트로이드를 구하는 코드

int get_cent(int v,int p,int S){
	for(auto[nxt,w]:g[v]) if(ok(nxt) && siz[nxt]*2>S) return get_cent(nxt,v,S);
	return v;
}

(3) v를 루트로 하는 트리에서 문제의 정답을 구하는 코드

int dnc(int v){
	int cent = get_cent(v,-1,get_siz(v));
    int ans = 0;
	// do something i.e) ans += dfs(v)
	vis[cent] = 1;
	for(auto[nxt,w]:g[cent]) if(!vis[nxt]) ans += dnc(nxt);
    return ans;
}

5. 자료

대표 문제: BOJ 5820 경주
소스: www.acmicpc.net/source/share/2c5be3a564f9419c8b6e5ac73b606b2d

www.youtube.com/watch?v=7v65lpxSdIY

justicehui.github.io/hard-algorithm/2020/08/25/centroid/

Centroid Decomposition