#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
x--; y--;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> best(n + 1, 0);
vector<set<pair<int, int>>> st(n); // {size, dist}
vector<int> off(n); // add how much to dist
vector<int> ss(n, 1);
// which set, size to add, distance to add
function<void(int, int, int)> upd_ans = [&] (int i, int s, int add) -> void {
cout << "???? " << i << ' ' << s << ' ' << add << '\n';
auto it = st[i].lower_bound({s, -inf});
if (it != st[i].end()) {
int fs = min(s, (*it).first);
// cout << "? " << fs << ' ' << (*it).second + off[i] + add << '\n';
best[fs] = max(best[fs], (*it).second + off[i] + add);
}
if (it != st[i].begin()) {
it--;
int fs = min(s, (*it).first);
best[fs] = max(best[fs], (*it).second + off[i] + add);
}
};
// set y into set x
function<void(int, int)> merge = [&] (int x, int y) -> void {
cout << "MERGE | " << x << ' ' << y << '\n';
if (st[x].size() < st[y].size()) {
swap(st[x], st[y]);
swap(off[x], off[y]);
cout << "SWAP\n";
}
for (auto [sz, dist]: st[y]) {
upd_ans(x, sz, dist + off[y]);
}
for (auto [sz, dist]: st[y]) {
dist += off[y] - off[x];
auto it = st[x].lower_bound({sz, -inf});
if (it != st[x].end()) {
if ((*it).second >= dist) {
continue;
}
}
st[x].insert({sz, dist});
while (true) {
it = st[x].lower_bound({sz, dist});
if (it == st[x].begin()) break;
it--;
if ((*it).second <= dist) {
st[x].erase(it);
} else {
break;
}
}
}
};
auto dbg = [&] (int x) -> void {
cout << "\nDBG ------- " << x << " -------\n";
cout << "OFF " << off[x] << '\n';
for (auto [z, y]: st[x]) {
cout << z << ' ' << y << '\n';
}
cout << "\n";
};
function<void(int, int)> dfs = [&] (int x, int p) -> void {
for (auto y: g[x]) {
if (y != p) {
dfs(y, x);
ss[x] += ss[y];
}
}
cout << "AT NODE " << x << '\n';
off[x] = 0;
for (auto y: g[x]) {
if (y != p) {
merge(x, y);
}
}
off[x]++;
st[x].insert({ss[x], 1 - off[x]});
// cout << "PAR\n";
upd_ans(x, n - ss[x], 0);
dbg(x);
};
dfs(0, -1);
for (int i = n - 1; i >= 0; --i) {
best[i] = max(best[i], best[i + 1]);
}
for (int i = 1; i <= n; ++i) {
if (i % 2) {
cout << 1 << '\n';
} else {
cout << best[i / 2] + 1 << '\n';
}
}
return 0;
}
10
1 2
1 4
3 4
1 5
2 6
2 7
2 8
2 9
3 10
