#include <bits/stdc++.h> using namespace std; int n; const int MAXN = 200005; vector<int> v[MAXN]; int used[MAXN]; // used for BFS distances (1-based) int a[MAXN], b[MAXN]; int lead, bot; int psub[MAXN]; // sizes of hanging subtrees per diameter node int ind[MAXN]; vector<int> dp[MAXN]; int otg[MAXN]; int mid1, mid2; void speed() { ios::sync_with_stdio(false); cin.tie(nullptr); } void bfs(int beg) { for (int i = 1; i <= n; ++i) used[i] = 0; queue<int> q; used[beg] = 1; q.push(beg); while (!q.empty()) { int w = q.front(); q.pop(); for (int nb : v[w]) { if (!used[nb]) { used[nb] = used[w] + 1; q.push(nb); } } } } void clea(int beg, int par) { used[beg] = 0; for (int nb : v[beg]) { if (nb == par) continue; clea(nb, beg); } } void prec() { int to = bot, nex = 0, par = 0; while (to != lead) { for (int nb : v[to]) { if (nb == par) continue; if (used[nb] != used[to] - 1) { clea(nb, to); } else nex = nb; } par = to; to = nex; } } void calc_subsizes(int beg, int leadnode, int par) { psub[leadnode]++; for (int nb : v[beg]) { if (!used[nb] && nb != par) calc_subsizes(nb, leadnode, beg); } } int check_count(int mi) { int br = 0; for (int i = 1; i <= n; ++i) { if (used[i] && used[i] <= mi) br += psub[i]; } return br; } void find_mid() { int L = 1, R = used[bot], mi; while (L <= R) { mi = (L + R) / 2; if (check_count(mi) >= (n + 1) / 2) R = mi - 1; else L = mi + 1; } // compute safe values for check(L) and check(L-1) int cL = check_count(L); int cLm1 = (L - 1 >= 0 ? check_count(L - 1) : 0); int dist1, dist2; if (min(cL, n - cL) >= min(cLm1, n - cLm1)) { dist1 = L; dist2 = L + 1; } else { dist1 = L - 1; dist2 = L; } // find nodes with used == dist1 / dist2 (if any) mid1 = -1; mid2 = -1; for (int i = 1; i <= n; ++i) { if (used[i] == dist1 && mid1 == -1) mid1 = i; if (used[i] == dist2 && mid2 == -1) mid2 = i; } // if not found (edge cases), fall back to endpoints near center of diameter if (mid1 == -1) mid1 = lead; if (mid2 == -1) mid2 = bot; } void get_dp(int beg, int par, int level) { ind[beg] = beg; // gather children excluding parent vector<int> children; for (int nb : v[beg]) if (nb != par) children.push_back(nb); if (children.empty()) { // real leaf dp[beg].clear(); dp[beg].push_back(level); ind[beg] = beg; return; } // process children for (int child : children) { get_dp(child, beg, level + 1); // pick the child with largest dp vector as representative if (dp[ind[beg]].size() < dp[ind[child]].size()) { ind[beg] = ind[child]; } } // Now merge other children into dp[ind[beg]] (small-to-large) int sum = 1; for (int child : children) { if (ind[child] == ind[beg]) continue; int sz = (int)dp[ind[child]].size(); sum += sz; // dp[ind[beg]] should be >= dp[ind[child]] in size because we chose largest as ind[beg] for (int j = 0; j < sz; ++j) { if (j < (int)dp[ind[beg]].size()) { otg[j] = max(otg[j], dp[ind[beg]][j] + dp[ind[child]][j] - level * 2 + 1); dp[ind[beg]][j] = max(dp[ind[beg]][j], dp[ind[child]][j]); } } } // extend dp[ind[beg]] by 'sum' copies of level (as original logic intended) for (int i = 1; i <= sum; ++i) dp[ind[beg]].push_back(level); } int main() { speed(); if (!(cin >> n)) return 0; for (int i = 1; i <= n; ++i) { v[i].clear(); used[i] = 0; psub[i] = 0; ind[i] = 0; dp[i].clear(); otg[i] = 0; } for (int i = 1; i < n; ++i) { cin >> a[i] >> b[i]; v[a[i]].push_back(b[i]); v[b[i]].push_back(a[i]); } // find diameter endpoints bfs(1); int ma = 0; for (int i = 1; i <= n; ++i) { if (used[i] > ma) { ma = used[i]; lead = i; } } bfs(lead); ma = 0; for (int i = 1; i <= n; ++i) { if (used[i] > ma) { ma = used[i]; bot = i; } } // prune non-diameter subtrees (used[] marks diameter nodes with distances) prec(); // compute subtree sizes hanging from each diameter node for (int i = 1; i <= n; ++i) { if (used[i]) { // use i as root of its hanging subtree, accumulate count into psub[i] calc_subsizes(i, i, 0); } } // choose mid nodes on diameter find_mid(); // clear dp/otg again to be safe (they were zeroed initially) for (int i = 1; i <= n; ++i) { dp[i].clear(); ind[i] = 0; } // compute dp from both midpoints // If mid1 == mid2, call once if (mid1 == mid2) { get_dp(mid1, 0, 1); } else { get_dp(mid1, mid2, 1); get_dp(mid2, mid1, 1); } // fill default for otg (fallback 1 where no better found) for (int i = 0; i <= n; ++i) if (!otg[i]) otg[i] = 1; // prepare representative indices for mid1/mid2 int rep1 = ind[mid1]; int rep2 = ind[mid2]; // output answers: one per line for (int k = 1; k <= n; ++k) { if (k % 2 == 1) { cout << 1 << '\n'; } else { int idx = k / 2 - 1; int s1 = (rep1 ? (int)dp[rep1].size() : 0); int s2 = (rep2 ? (int)dp[rep2].size() : 0); int ans; if (idx >= 0 && min(s1, s2) > idx) { ans = max(dp[rep1][idx] + dp[rep2][idx], otg[idx]); } else { // take whichever has the idx (if any) else use otg int val1 = (idx >= 0 && s1 > idx ? dp[rep1][idx] : 0); int val2 = (idx >= 0 && s2 > idx ? dp[rep2][idx] : 0); ans = max(otg[idx], max(val1, val2)); } cout << ans << '\n'; } } return 0; }