BOJ 24029 - 정기 모임 3

BOJ 24029 - 정기 모임 3

에디토리얼 에서 전반적인 아이디어는 얻도록 하자.

이 글에선 실제로 구현하는 방법을 조금 알아볼 예정이다.

부모 방향으로 DFS를 돌린다는 것이 뭔말인가 싶은데, 실제로 그렇게 역방향으로 DFS를 돌리는 것은 아니고, 다음과 같이 루트로부터 DFS를 시행한다는 의미이다.

1. 루트로부터 DFS를 시행한다.
2. 자신의 자식들을 순회하기 전에 부모의 $dp$ 값을 이용한다.
   1. 이 과정에서 부모의 $dp$값 뿐아닌, 부모의 자식들 중 자신이 아닌 자식들에 대한 어떤 값을 이용하는 것일 수도 있다.
3. 자식들을 순회한다.

이렇게 하면 결국 어떤 정점에선 자신의 자식들과 자신의 부모에 대해서 모든 방향의 경로에 대한 어떤 값을 유지할 수 있고, 이걸 취합하거나 해서 필요한 쿼리에 사용할 수 있다.

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 ans(n * 2 + 5);

   // 부모 방향으로의 최대 깊이
   vi dp_up(n);
   // 자식들 중 최대 깊이
   vvi sub_depth(n);

   function<void(int, int)> fn = [&](int cur, int p) -> void {
      sub_depth[cur].pb(0);
      for (int to: edges[cur]) {
         if (to == p) continue;
         fn(to, cur);
         sub_depth[cur].push_back(sub_depth[to].back() + 1);
      }
      sort(all(sub_depth[cur]));
   };
   fn(0, -1);

   function<void(int, int)> fn2 = [&](int cur, int p) -> void {

      if (p != -1) {
         dp_up[cur] = dp_up[p] + 1;
         if (sub_depth[p].back() == sub_depth[cur].back() + 1) {
            maxa(dp_up[cur], sub_depth[p][sz(sub_depth[p]) - 2] + 1);
         } else {
            maxa(dp_up[cur], sub_depth[p][sz(sub_depth[p]) - 1] + 1);
         }
      }

      for (int to: edges[cur]) {
         if (to == p) continue;
         fn2(to, cur);
      }

   };
   fn2(0, -1);
   int diameter = 0;
   for (int i = 0; i < n; i++) {
      sub_depth[i].pb(dp_up[i]);
      sort(all(sub_depth[i]));

      int s = sz(sub_depth[i]);
      for (int j = s - 1; j >= 1;) {
         int k = j;
         while (k >= 1 && sub_depth[i][j] == sub_depth[i][k])k--;

         int cnt = s - k - 1;
         assert(sub_depth[i][j] <= n);
         maxa(ans[sub_depth[i][j] * 2], cnt);
         maxa(diameter, sub_depth[i][j]);
         j = k;
      }
   }
   for (int i = n - 1; i >= 0; i--) maxa(ans[i], ans[i + 1]);
   for (int i = 1; i <= n; i++) {
      if (i % 2 == 0) {
         cout << max(1, ans[i]) << endl;
      } else {
         if (i <= diameter) cout << 2 << endl;
         else cout << 1 << endl;
      }
   }
}