#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> adj, ct, spt;
struct cent_decomposition {
int n, rt;
vector<vector<int>> adj, ct;
vector<int> c1, c2, sub;
void paint(int u, int p, int lv) {
sub[u]=1;
c1[u]=lv;
for (int i:adj[u]) if (i!=p&&!c2[i]) paint(i, u, lv), sub[u]+=sub[i];
}
int get_cent(int u, int p, int s) {
for (int i:adj[u]) if (i!=p&&!c2[i]&&sub[i]>s) return get_cent(i, u, s);
return u;
}
void build() {
int cnt=0, lv=0;
while (cnt<n&&++lv) for (int i=1; i<=n; i++) if (!c2[i]&&c1[i]!=lv) {
paint(i, 0, lv);
int cent=get_cent(i, 0, sub[i]/2);
c2[cent]=1;
cnt++;
}
}
void push(int u, int p, int a) {
if (c1[u]==c1[a]+1) ct[a].emplace_back(u);
for (int v:adj[u]) if (v!=p&&c1[v]>c1[a]) push(v, u, a);
}
cent_decomposition(int n) : n(n), ct(n+1), adj(n+1), c1(n+1), c2(n+1), sub(n+1) {
for (int i=1, u, v; i<n; i++) cin>>u>>v, adj[u].emplace_back(v), adj[v].emplace_back(u);
build();
for (int i=1; i<=n; i++) push(i, 0, i);
for (int i=1; i<=n; i++) if (c1[i]==1) rt=i;
::adj=adj;
::ct=ct;
}
};
int ord;
vector<int> sz, dep, in, out, ans;
void dfs1(int u, int p) {
if (u!=1) dep[u]=dep[p]+1;
spt[u].emplace_back(p);
for (int i=0; i<spt[spt[u][i]].size(); i++) spt[u].emplace_back(spt[spt[u][i]][i]);
in[u]=++ord;
for (int v:adj[u]) if (v!=p) dfs1(v, u), sz[u]+=sz[v];
out[u]=ord;
}
int op(int u, int v) {
if (in[u]<=in[v]&&out[v]<=out[u]) {
for (int i=17; i>=0; i--) if (i<spt[v].size()&&dep[spt[v][i]]>dep[u]) v=spt[v][i];
return n-sz[v];
}
return sz[u];
}
int dist(int u, int v) {
if (dep[u]>dep[v]) swap(u, v);
int rt=dep[v]-dep[u];
for (int i=0; (1<<i)<=rt; i++) if (rt&(1<<i)) v=spt[v][i];
if (u==v) return rt;
for (int i=17; i>=0; i--) if (i<spt[u].size()&&spt[u][i]!=spt[v][i]) u=spt[u][i], v=spt[v][i], rt+=(1<<i+1);
return rt+2;
}
void dfs2(int u) {
vector<array<pair<int, int>, 2>> em;
vector<int> to;
auto ins = [&](int i, int v, int j) {
if (em.size()<=i) em.resize(i+1);
for (int k:{0, 1}) if (em[i][k].second==j) {
em[i][k].first=max(em[i][k].first, v);
if (em[i][0].first<em[i][1].first) swap(em[i][0], em[i][1]);
return ;
}
if (em[i][0].first<v) em[i][1]=em[i][0], em[i][0]={v, j};
else if (em[i][1].first<v) em[i][1]={v, j};
};
for (int v:ct[u]) dfs2(v);
ins(1, 0, u);
for (int v:ct[u]) {
ct[v].emplace_back(v);
for (int w:ct[v]) to.emplace_back(w);
int xx=op(u, v);
vector<pair<int, int>> im;
for (int w:ct[v]) {
int o=op(w, u);
int d=dist(w, u);
ans[min(xx, o)*2]=max(ans[min(xx, o)*2], d+1);
im.emplace_back(o, d);
}
sort(im.rbegin(), im.rend());
int mx=0;
for (auto [i, w]:im) if (mx<w) mx=w, ins(i, w, v);
}
swap(to, ct[u]);
for (int i=em.size()-1; i; i--) {
ans[i*2]=max(ans[i*2], em[i][0].first+em[i][1].first+1);
for (int j:{0, 1}) ins(i-1, em[i][j].first, em[i][j].second);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>>n;
auto ct=cent_decomposition(n);
sz.resize(n+1, 1);
spt.resize(n+1);
in=out=ans=dep=sz;
dfs1(1, 0);
dfs2(ct.rt);
for (int i=(n&~1)-2; i>0; i-=2) ans[i]=max(ans[i+2], ans[i]);
for (int i=1; i<=n; i++) cout<<ans[i]<<'\n';
return 0;
}
Compilation message
meetings2.cpp: In constructor 'cent_decomposition::cent_decomposition(int)':
meetings2.cpp:10:27: warning: 'cent_decomposition::ct' will be initialized after [-Wreorder]
10 | vector<vector<int>> adj, ct;
| ^~
meetings2.cpp:10:22: warning: 'std::vector<std::vector<int> > cent_decomposition::adj' [-Wreorder]
10 | vector<vector<int>> adj, ct;
| ^~~
meetings2.cpp:39:2: warning: when initialized here [-Wreorder]
39 | cent_decomposition(int n) : n(n), ct(n+1), adj(n+1), c1(n+1), c2(n+1), sub(n+1) {
| ^~~~~~~~~~~~~~~~~~
meetings2.cpp: In function 'void dfs1(int, int)':
meetings2.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i=0; i<spt[spt[u][i]].size(); i++) spt[u].emplace_back(spt[spt[u][i]][i]);
| ~^~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp: In function 'int op(int, int)':
meetings2.cpp:63:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i=17; i>=0; i--) if (i<spt[v].size()&&dep[spt[v][i]]>dep[u]) v=spt[v][i];
| ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int dist(int, int)':
meetings2.cpp:74:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i=17; i>=0; i--) if (i<spt[u].size()&&spt[u][i]!=spt[v][i]) u=spt[u][i], v=spt[v][i], rt+=(1<<i+1);
| ~^~~~~~~~~~~~~~
meetings2.cpp:74:106: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
74 | for (int i=17; i>=0; i--) if (i<spt[u].size()&&spt[u][i]!=spt[v][i]) u=spt[u][i], v=spt[v][i], rt+=(1<<i+1);
| ~^~
meetings2.cpp: In lambda function:
meetings2.cpp:82:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<std::pair<int, int>, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
82 | if (em.size()<=i) em.resize(i+1);
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
328 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
328 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
328 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
