#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 2e5 + 5;
vector<int> ad[mxN];
int sz[mxN];
int p[mxN][20];
int d[mxN];
int n;
void dfs(int u, int par) {
sz[u] = 1;
for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i - 1]][i - 1];
for (int v : ad[u]) {
if (v == par) continue;
p[v][0] = u;
d[v] = d[u] + 1;
dfs(v, u);
sz[u] += sz[v];
}
}
int get(int u, int par) {
for (int v : ad[u]) {
if (v == par) continue;
if (sz[v] * 2 > n) return get(v, u);
}
return u;
}
int lca(int u, int v) {
if (d[u] < d[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (d[p[u][i]] >= d[v]) u = p[u][i];
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
}
return p[u][0];
}
int dist(int a, int b) {
return d[a] + d[b] - 2 * d[lca(a, b)];
}
void testCase() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
ad[u].push_back(v);
ad[v].push_back(u);
}
dfs(1, -1);
int c = get(1, -1);
c = 1;
p[c][0] = c;
d[c] = 0;
dfs(c, -1);
vector<int> ans(n + 1);
vector<int> v[n + 1];
for (int i = 1; i <= n; i++) {
v[sz[i]].push_back(i);
}
int a = c, b = c, d = 0;
for (int i = n; i >= 1; i--) {
for (int o : v[i]) {
int ao = dist(a, o);
int bo = dist(b, o);
if (max(ao, bo) > d) {
if (ao > bo) {
d = ao;
b = o;
} else {
d = bo;
a = o;
}
}
}
ans[i] = max(ans[i], d + 1);
ans[i - 1] = max(ans[i - 1], ans[i]);
}
for (int i = 1; i <= n; i++) {
if (i & 1) cout << "1\n";
else cout << ans[i / 2] << "\n";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
testCase();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
5028 KB |
Output is correct |
3 |
Correct |
4 ms |
4948 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
5028 KB |
Output is correct |
3 |
Correct |
4 ms |
4948 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
5028 KB |
Output is correct |
3 |
Correct |
4 ms |
4948 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |