센트로이드 분할 (Centroid Decomposition)

1차원 배열에서 중간점을 기준으로 두조각으로 분할해서 분할정복을 하는 것과 같은 원리이다.

1) 임의의 노드를 루트로 잡고, 모든 노드에 대해서 그 노드를 루트로 하는 서브트리의 크기를 계산한다.

2) 루트에서부터 출발해서, 현재 노드에 달려있는 서브트리중 크기가 N/2 초과인것이 있는지 찾는다. 그런 서브트리가 없으면, 그 노드가 센트로이드. 그런 서브트리가 있으면 그 노드를 현재 노드로 세팅하고 다시 2)를 반복.

총 시간복잡도는 O(n)