BOJ 12896 - 스크루지 민호

BOJ 12896 - 스크루지 민호

트리의 지름을 찾은 다음에, 그 지름의 길이가 $L$ 이라면 정답은 $\left\lceil \dfrac{L}{2} \right\rceil$ 임을 알 수 있다.

void solve() {
   int n;
   cin >> n;
   vvi edges(n);
   for (int i = 0, u, v; i < n - 1; i++) cin >> u >> v, u--, v--, edges[u].pb(v), edges[v].pb(u);

   vi dist(n);
   function<void(int, int)> fn = [&](int i, int p) -> void {
      for (int to: edges[i]) {
         if (to != p) {
            dist[to] = dist[i] + 1;
            fn(to, i);
         }
      }
   };
   fn(0, -1);
   int j = 0;
   for (int i = 0; i < n; i++) if (dist[j] < dist[i]) j = i;
   fill(all(dist), 0);
   fn(j, -1);
   int k = 0;
   for (int i = 0; i < n; i++) if (dist[k] < dist[i]) k = i;
   cout << (dist[k] + 1) / 2;
}