Submission #474911

#	Time	Username	Problem	Language	Result	Execution time	Memory
474911		600Mihnea	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4037 ms	14564 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
int n, sub[N], sol[N];
vector<int> g[N];

void build(int a, int p = -1) {
  sub[a] = 1;
  for (auto &b : g[a]) {
    if (b == p) continue;
    build(b, a);
    sub[a] += sub[b];
  }
}

void dfs(int a, int p, int thr, int len) {
  sol[min(thr, sub[a])] = max(sol[min(thr, sub[a])], len);
  for (auto &b : g[a]) {
    if (b == p) continue;
    dfs(b, a, thr, len + 1);
  }

}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }

  for (int root = 1; root <= n; root++) {
    build(root);
    for (auto &i : g[root]) {
      dfs(i, root, n - sub[i], 1);
    }
  }

  for (int i = n; i >= 1; i--) {
    sol[i] = max(sol[i], sol[i + 1]);
  }

  for (int i = 1; i <= n; i++) {
    if (i & 1) {
      cout << 1 << "\n";
    } else {
      cout << sol[i / 2] + 1 << "\n";
    }
  }

  return 0;
}

/**

**/

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 0 / 80