#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int logn = log2(maxn) + 1;
vector<int> adj[maxn];
int par[logn][maxn], sz[maxn], dep[maxn], c[maxn];
void dfs1(int curnode, int prvnode, int d = 1) {
par[0][curnode] = prvnode;
for (int i = 1; i < logn; i++) par[i][curnode] = par[i - 1][par[i - 1][curnode]];
sz[curnode] = 1;
dep[curnode] = d;
for (auto v : adj[curnode]) if (v != prvnode) {
dfs1(v, curnode, d + 1);
sz[curnode] += sz[v];
}
}
int dfs2(int curnode, int prvnode) {
for (auto v : adj[curnode]) if (v != prvnode && sz[v] > sz[0] / 2) return dfs2(v, curnode);
return curnode;
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
for (int i = logn - 1; i >= 0; i--) if (dep[a] <= dep[b] - (1 << i)) b = par[i][b];
if (a == b) return a;
for (int i = logn - 1; i >= 0; i--) if (par[i][a] != par[i][b]) {
a = par[i][a];
b = par[i][b];
}
return par[0][a];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0, a, b; i < n - 1; i++) {
cin >> a >> b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs1(0, 0);
int cen = dfs2(0, 0);
int l = cen, r = cen;
vector<pair<int, int>> vec;
for (int i = 0; i < n; i++) vec.push_back({sz[i], i});
sort(vec.rbegin(), vec.rend());
int ans[n + 1], cur = 1;
fill(ans, ans + n + 1, 0);
for (int i = 0; i < n; i++) {
int idx = vec[i].second;
int d1 = dep[l] + dep[idx] - 2 * dep[lca(l, idx)] + 1;
int d2 = dep[r] + dep[idx] - 2 * dep[lca(r, idx)] + 1;
if (d1 < d2) {
swap(d1, d2);
swap(l, r);
}
if (d1 > cur) {
cur = d1;
r = idx;
}
ans[vec[i].first] = cur;
}
for (int i = n - 1; i >= 0; i--) ans[i] = max(ans[i], ans[i + 1]);
for (int i = 1; i <= n; i++) {
if (i & 1) cout << "1" << '\n';
else cout << ans[i >> 1] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
