Centroid Decomposition

트리에서 분할정복을 해보자. 그러기 위해서는 트리의 중앙을 찾은 후, 그 중앙을 기준으로 나누어진 부분들의 크기가 충분히 작도록 해야 한다. 이 '중앙'을 centroid라 한다. 구체적으로는, 트리에서 centroid를 제거하여 생기는 forest에서는 모든 트리의 크기가 원래 트리의 절반이하가 된다. 트리의 centroid는 1개 또는 2개이고, 2개일 경우에는 그 2개가 인접하다. 

트리에서 centroid를 잡은 후, 그 centroid를 제거하자. 그 후 나누어진 서브트리들에서 다시 centroid를 잡자. 이 과정을 반복하면 분할정복이 가능하다. 또는 centroid를 잡은 과정을 나타내면 centroid tree가 된다. 

자세한 내용은 https://koosaga.com/145 참고.

 

내 코드

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

typedef pair<int, int> pii;

#define fi first
#define se second

const int MAXN = 200010;

vector<pii> ed[MAXN];
int sz[MAXN];
bool vis[MAXN];

void dfs(int x, int p) {				// 서브트리들의 크기를 구한다
	sz[x] = 1;
	for(auto a : ed[x]) if(!vis[a.se] && a.se != p) {
		dfs(a.se, x);
		sz[x] += sz[a.se];
	}
}

void solve(int x) {					// x를 포함하는 서브트리에서 문제 해결
	dfs(x, -1);					// x를 루트로 하는 트리에서 각 서브트리의 크기 구함
	int s = sz[x];
	while(1) {					// x <- centroid
		bool b = false;
		for(auto a : ed[x]) if(!vis[a.se] && sz[a.se] < sz[x] && 2 * sz[a.se] >= s) {
			x = a.se;
			b = true;
			break;
		}
		if(!b) break;
	}
	//TODO
	vis[x] = true;					// x를 보았다고 확인
	for(auto a : ed[x]) if(!vis[a.se]) solve(a.se);	// 나누어진 서브트리에서 문제 해결
}