Problem

https://www.acmicpc.net/problem/5820

Idea

트리의 Centroid: N개의 노드를 가지는 트리에서 특정 노드를 지웠을 때 나눠지는 subtree의 node개수가 각각 N/2 이하라면 그 특정 노드를 트리의 centroid 라고한다.

centroid node를 구하는 방법

1. 임의의 root node를 택하고 dfs를 통해 각 node별 subtree 의 size를 구한다

   static int getSz(int curr, int parent) {
       sz[curr] = 1;
           
       for (int next : adj.get(curr)) {
           if (curr == next) {
               continue;
           }
           sz[curr] += getSz(next, curr);
       }
       return sz[curr];
   }
   

2. 임의의 root node로부터 subtree size가 N/2 개보다 큰 node가 없을 때까지 탐색을 진행

   static int getCenter(int here, int parent, int cap) {
        for (int next: adj.get(here)) {
            if (here == next) { 
                continue;
            }
            if (sz[next] > cap) {
                return getCenter(next, here, cap);
            }
        }
        return here;
   }