Centroid에 관하여
Centroid는 트리의 중심을 의미한다. 모든 이웃의 서브트리의 크기가 전체 트리 크기의 절반 이하가 되도록 하는 정점을 의미한다. 그렇기 때문에 용도가 재귀적이다. 트리에서 $O(N)$이나 $O(NlogN)$ 수준에서 문제의 조건을 만족하는 단 하나의 경로를 찾아야하는 문제에 대해서는 무조건 센트로이드를 떠올려야 한다. 센트로이드의 정의를 이용한 예제 https://codeforces.com/contest/1205/problem/D Problem - D - Codeforces codeforces.com 좋은 수학문제다. 센트로이드를 중심으로 이웃 노드를 2개의 파티션으로 분할하여 서브트리의 크기 합이 각각 $N/3$와 $2N/3$ 사이에 오도록 만들 수 있다. 각각의 수를 $a$와 $b$라고 하면, ..
