#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;
struct no{
vector<int> ch;
int as[20]={0};
int dep=-1;
int sz;
};
vector<no> v;
void dfs(int r,int f){
v[r].dep=v[f].dep+1;
v[r].as[0]=f;
v[r].sz=1;
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r);
v[r].sz+=v[h].sz;
}
}
}
void gas(int n){
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
v[j].as[i]=v[v[j].as[i-1]].as[i-1];
}
}
}
int fc(int r,int f,int nz){
for(auto h:v[r].ch){
if(h!=f){
if(v[h].sz>nz/2){
return fc(h,r,nz);
}
}
}
return r;
}
int dia=0,cz=0,e=0,f=0;
int lca(int x,int y){
if(v[x].dep<v[y].dep){
swap(x,y);
}
if(v[x].dep>=v[y].dep){
for(int i=19;i>=0;i--){
if(v[v[x].as[i]].dep>=v[y].dep){
x=v[x].as[i];
}
}
}
for(int i=19;i>=0;i--){
if(v[x].as[i]!=v[y].as[i]){
x=v[x].as[i];
y=v[y].as[i];
}
}
return v[x].as[0];
}
int dis(int x,int y){
int u=lca(x,y);
return v[x].dep+v[y].dep-2*v[u].dep;
}
void add(int z){
int x=dis(z,e);
int y=dis(z,f);
int a,b;
if(x>y){
a=e;
b=x;
}
else{
a=f;
b=y;
}
if(b>dia){
dia=b;
if(e==a){
f=z;
}
else{
e=z;
}
}
}
int main(){
AquA;
int n;
cin >> n;
v.resize(n);
for(int i=1;i<n;i++){
int a,b;
cin >> a >> b;
a--;
b--;
v[a].ch.push_back(b);
v[b].ch.push_back(a);
}
dfs(0,0);
int ct=fc(0,0,n);
dfs(ct,ct);
gas(n);
vector<pair<int,int> > vp;
for(int i=0;i<n;i++){
vp.push_back({v[i].sz,i});
}
sort(vp.begin(),vp.end(),greater<pair<int,int> >());
vector<int> ans(n+1);
add(ct);
assert(vp[0].sc==ct);
e=ct;
f=ct;
cz++;
for(int i=1;i<=n;i+=2){
ans[i]=1;
}
for(int i=n-n%2;i>=2;i-=2){
while(cz<n){
if(vp[cz].fs<i/2){
break;
}
add(vp[cz].sc);
cz++;
}
ans[i]=dia+1;
}
for(int i=1;i<=n;i++){
cout << ans[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
