#include <bits/stdc++.h>
#define vi vector <int>
#define pb push_back
using namespace std;
struct LCA{
vi st, ed, _lg, high;
vector <vi> euler, adj;
int cnt;
void dfs(int u, int pa){
++ cnt;
st[u] = cnt;
euler[cnt].pb(u);
for (int v : adj[u]){
if (v == pa) continue;
high[v] = high[u] + 1;
dfs(v, u);
euler[++ cnt].pb(u);
}
ed[u] = cnt;
}
int check(int u, int v) {
return st[u] <= st[v] && ed[v] <= ed[u];
}
int min_by_time(int u, int v) {
return (st[u] < st[v] ? u : v);
}
void add(int u, int v){
adj[u].pb(v);
adj[v].pb(u);
}
LCA(int n){
st.resize(n + 3, 0);
ed.resize(n + 3, 0);
euler.resize(3 * n + 5);
adj.resize(n + 3);
_lg.resize(3 * n + 5);
high.resize(n + 3, 1);
for (int i = 0; i <= 3 * n; ++ i) _lg[i] = log2(i);
}
void init(int r){
cnt = 0;
dfs(r, 0);
for (int lg = 1; lg < 20; ++lg) {
for (int i = 1; i + (1 << lg) - 1 <= cnt; ++i)
euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
}
}
int get(int u, int v) {
int L = min(st[u], st[v]);
int R = max(ed[u], ed[v]);
int lg = _lg[R - L + 1];
return min_by_time(euler[L][lg], euler[R - (1 << lg) + 1][lg]);
}
int dist(int u, int v){
int lc = get(u, v);
return high[u] + high[v] - 2 * high[lc];
}
};
const int N = 2e5 + 5;
int n, sz[N];
vector <int> adj[N];
void dfs(int u, int p = -1){
sz[u] = 1;
for (int v : adj[u]){
if (v == p) continue;
dfs(v, u); sz[u] += sz[v];
}
}
int find_cen(int u, int p = -1){
for (int v : adj[u]){
if (v == p) continue;
if (sz[v] * 2 > n) return find_cen(v, u);
}
return u;
}
vector <int> cur[N / 2];
int ans[N];
void solve(){
cin >> n;
LCA tree(n);
for (int i = 1, u, v; i < n; ++ i){
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
tree.add(u, v);
}
dfs(1);
int r = find_cen(1);
tree.init(r); dfs(r);
for (int i = 1; i <= n; ++ i) {
if (i != r) cur[sz[i]].push_back(i);
if (i & 1) ans[i] = 1;
}
int u = r, v = r, Max = 0;
for (int i = n / 2; i >= 1; -- i){
for (int k : cur[i]){
if (tree.dist(u, k) < tree.dist(v, k)) swap(u, v);
if (tree.dist(u, k) > Max){
Max = tree.dist(u, k);
v = k;
}
}
ans[i * 2] = Max + 1;
}
for (int i = 1; i <= n; ++ i) cout << ans[i] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
meetings.cpp: In member function 'void LCA::init(int)':
meetings.cpp:53:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
53 | euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
| ~~~^~~
/usr/bin/ld: /tmp/ccf9mz7i.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccAQSlk.o:meetings.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccf9mz7i.o: in function `main':
grader.cpp:(.text.startup+0x15b): undefined reference to `Solve(int)'
collect2: error: ld returned 1 exit status
