// compile: g++ -o data data.cpp -std=gnu++20 -DLOCAL
// run: ./data < data.in
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#endif
#define sz(v) ((int)(v).size())
#define PV(v) for (int i=0;i<v.size();++i)cout<<v[i]<<" ";cout<<endl;
#define INTINF 9223372036854775807
#define int long long
#define MAXN 100010
using namespace std;
struct node {
int dis, id;
};
vector<node> dis;
vector<vector<int>> e;
vector<int> disx, disy;
vector<int> vis;
int n, root = 0;
int x, y;
void dfs(int u, vector<int> &dis, int s) {
vis[u] = 1;
dis[u] = s;
for (int i = 0; i < e[u].size(); ++i) {
if (vis[e[u][i]]) continue;
dfs(e[u][i], dis, s + 1);
}
}
bool cmp(struct node a, struct node b) {return a.dis < b.dis; }
int find(int k) {
int l = 0, r = n - 1;
int ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (dis[mid].dis <= k) l = mid + 1;
else ans = mid, r = mid - 1;
}
return ans;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
dis.resize(n); disx.resize(n); disy.resize(n); vis.resize(n); e.resize(n);
for (int i = 0; i < n-1; ++i) {
int u, v; cin >> u >> v;
--u; --v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(root, disx, 0);
x = distance(disx.begin(), max_element(disx.begin(), disx.begin() + n));
fill(vis.begin(), vis.end(), 0);
dfs(x, disx, 0);
y = distance(disx.begin(), max_element(disx.begin(), disx.begin() + n));
fill(vis.begin(), vis.end(), 0);
dfs(y, disy, 0);
for (int i = 0; i < n; ++i) dis[i] = node{max(disx[i], disy[i]), i + 1};
sort(dis.begin(), dis.end(), cmp);
// for (int i = 0; i < n; ++i) cout << dis[i].dis << " " << dis[i].id << endl;
for (int k = 0; k < n; ++k) {
int ans = find(k);
if (~ans) cout << ans + 1 << " \n"[k==n-1];
else cout << n << " \n"[k==n-1];
}
return 0;
}
No Comments