#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2e5+5;
int bj[nax][20];
int dep[nax];
int sz[nax];
vector<int> adj[nax];
int n;
void get_size(int x,int p){
sz[x]=1;
for(auto u:adj[x]){
if(u==p) continue;
bj[u][0]=x;
dep[u]=dep[x]+1;
get_size(u,x);
sz[x]+=sz[u];
}
return;
}
int centroid(int x,int p){
for(auto u:adj[x]){
if(u==p) continue;
if(sz[u]*2>n) return centroid(u,x);
}
return x;
}
void build(int x,int p){
for (int i = 1; i < 20; ++i)
{
bj[x][i]=bj[bj[x][i-1]][i-1];
}
for(auto u:adj[x]){
if(u==p) continue;
build(u,x);
}
}
int jump(int x,int d){
for (int i = 0; i < 20; ++i)
{
if(d&(1<<i)) x=bj[x][i];
}
return x;
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
x=jump(x,dep[x]-dep[y]);
if(x==y) return x;
for (int i = 19; i >= 0; --i)
{
int curx=bj[x][i];
int cury=bj[y][i];
if(cury!=curx){
x=curx;
y=cury;
}
}
return bj[x][0];
}
int dis(int x,int y){
return dep[x]+dep[y]-2*dep[lca(x,y)]+1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin>>n;
for (int i = 0; i < n-1; ++i)
{
int x,y;
cin>>x>>y;
x--;y--;
adj[x].pb(y);
adj[y].pb(x);
}
get_size(0,-1);
int cen=centroid(0,-1);
dep[cen]=0;
bj[cen][0]=cen;
get_size(cen,-1);
build(0,-1);
vector<int> tab[n+1];
for (int i = 0; i < n; ++i)
{
tab[sz[i]].pb(i);
}
int a=cen;
int b=cen;
int ans=0;
int res[n];
//cout <<dep[4]<<" "<<dep[0]<<" "<<lca(0,4)<<endl;
for (int i = n/2; i >=1 ; --i)
{
//cout <<"nabba"<<" "<<i<<endl;
for (int j = 0; j < tab[i].size(); ++j)
{
//cout <<tab[i][j]<<endl;
int nw=tab[i][j];
int x=dis(nw,a);
int y=dis(nw,b);
//cout <<x<<" "<<y<<" "<<a<<" "<<b<<endl;
if(ans<y){
a=nw;
ans=y;
}
if(ans<x){
b=nw;
ans=x;
}
}//cout <<endl;
res[i]=ans;
}
for (int i = 1; i <= n; ++i)
{
if(i%2) cout <<1<<endl;
else cout <<res[i/2]<<endl;
}
}
Compilation message
meetings2.cpp: In function 'int main()':
meetings2.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int j = 0; j < tab[i].size(); ++j)
| ~~^~~~~~~~~~~~~~~
meetings2.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
