#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+9;
vector<int>a[maxn],a1[maxn],a2[maxn];
//a1 add sub
//a2 reverse sub
int sub[maxn];
int rev[maxn];
int dep[maxn];
int st[maxn][19];
int in[maxn],out[maxn];
int tme=0;
int n;
void dfs(int u,int par){
sub[u]=1;
in[u]=++tme;
for(auto v:a[u]){
if (v==par)continue;
dep[v]=dep[u]+1;
st[v][0]=u;
for1(i,1,18)st[v][i]=st[st[v][i-1]][i-1];
dfs(v,u);
sub[u]+=sub[v];
}
rev[u]=n+1-sub[u];
out[u]=tme;
}
int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for1(i,0,18){
if (k>>i&1)u=st[u][i];
}
if (u==v)return u;
for2(i,18,0){
if (!st[u][i]||!st[v][i])continue;
if (st[u][i]!=st[v][i]){
u=st[u][i];
v=st[v][i];
}
}
return st[u][0];
}
int dis(int u,int v){
return dep[u]+dep[v]-2*dep[lca(u,v)]+1;
}
int ans[maxn];
bool t1[maxn],t2[maxn];
pii newdia(const pii &p,int u){
int x=p.fi,y=p.se,z=u;
int xy=dis(x,y),yz=dis(y,z),xz=dis(x,z);
int mx=max({xy,yz,xz});
if (mx==xy)return {x,y};
if (mx==yz)return {y,z};
if (mx==xz)return {x,z};
}
int it[maxn*4];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
it[id]=val;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
it[id]=max(it[id*2],it[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return it[id];
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
cin>>n;
for1(i,1,n-1){
int u,v;
cin>>u>>v;
a[u].pb(v);
a[v].pb(u);
}
dfs(1,0);
for1(i,1,n){
a1[sub[i]].pb(i);
a2[rev[i]].pb(i);
}
int cnt=0;
pii dia;
for2(i,n,1){
for (auto v:a1[i]){
t1[v]=1;
if (t2[v]){
cnt++;
//ver.pb(v);
if (cnt==1){
dia.fi=dia.se=v;
}
else {
dia=newdia(dia,v);
}
}
}
for (auto v:a2[i]){
t2[v]=1;
if (t1[v]){
cnt++;
//ver.pb(v);
if (cnt==1){
dia.fi=dia.se=v;
}
else {
dia=newdia(dia,v);
}
}
}
if (i*2<=n){
if (cnt>=1)ans[i*2]=dis(dia.fi,dia.se);
else ans[i*2]=1;
}
}
for1(i,1,n){
a2[i].clear();
}
for1(i,2,n){
a2[n-sub[i]].pb(i);
}
for1(i,1,n)t1[i]=0;
int nwdia=0;
for2(i,n,1){
for (auto v:a1[i]){
update(1,1,n,in[v],dep[v]);
int u=v;
for2(i1,18,0){
if (!st[u][i1])continue;
if (t1[st[u][i1]]){
u=st[u][i1];
}
}
u=st[u][0];
nwdia=max(nwdia,dep[v]-dep[u]+1);
}
for (auto v:a2[i]){
t1[v]=1;
int maxdep=get(1,1,n,in[v],out[v]);
nwdia=max(nwdia,maxdep-dep[v]+2);
}
if (i*2<=n){
ans[i*2]=max(ans[i*2],nwdia);
}
}
for1(i,1,n){
if (i%2==1)cout<<1<<'\n';
else cout<<ans[i]<<'\n';
}
}
Compilation message
meetings2.cpp: In function 'std::pair<int, int> newdia(const std::pair<int, int>&, int)':
meetings2.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
71 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14364 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14384 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14364 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14384 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14364 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14384 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
