#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int n;
int parent[200005],siz[200005],depth[200005];
vector<int> con[200005];
int anc[200005][18];
int cine[400005];
int tin[200005],tout[200005],timer;
vector<int> unde[200005];
void dfs(int nod)
{
tin[nod]=++timer;
cine[timer]=nod;
unde[nod].push_back(timer);
siz[nod]=1;
for(auto adj:con[nod])
{
if(adj!=parent[nod])
{
parent[adj]=nod;
anc[adj][0]=nod;
depth[adj]=depth[nod]+1;
dfs(adj);
cine[++timer]=nod;
unde[nod].push_back(timer);
siz[nod]+=siz[adj];
}
}
tout[nod]=timer;
}
struct node
{
int a,b,ab,bc,abc;
};
node combine(node x, node y)
{
node aux;
aux.a = max(x.a, y.a);
aux.b = max(x.b, y.b);
aux.ab = max({x.ab, y.ab, x.a+y.b});
aux.bc = max({x.bc, y.bc, x.b+y.a});
aux.abc = max({x.abc, y.abc, x.a+y.bc, x.ab+y.a});
return aux;
}
node aint[1100000];
void build(int nod, int st, int dr)
{
if(st==dr)
{
aint[nod] = {-INF,-INF,-INF,-INF,-INF};
return;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
void upd(int nod, int st, int dr, int poz, int newv)
{
if(st==dr)
{
aint[nod].a = newv;
aint[nod].b = -2*newv;
aint[nod].ab = aint[nod].bc = aint[nod].abc = -INF;
return;
}
int mij=(st+dr)/2;
if(poz<=mij) upd(nod*2,st,mij,poz,newv);
else upd(nod*2+1,mij+1,dr,poz,newv);
aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return {-INF,-INF,-INF,-INF,-INF};
if(le==st && dr==ri)
return aint[nod];
int mij=(st+dr)/2;
return combine(qry(nod*2,st,mij,le,min(mij,ri)),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int rez[200005];
signed main()
{
cin>>n;
int a,b;
for(int i=1;i<n;i++)
{
cin>>a>>b;
con[a].push_back(b);
con[b].push_back(a);
}
dfs(1);
build(1,1,timer);
for(int p=1;p<18;p++)
for(int i=1;i<=n;i++)
anc[i][p] = anc[anc[i][p-1]][p-1];
vector<pair<pair<int,int>,int>> v;
for(int i=1;i<=n;i++)
{
v.push_back({{-siz[i],0},i});
v.push_back({{-(n-siz[i]+1),1},i});
}
sort(v.begin(),v.end());
for(auto x:v)
{
int i=x.second;
int tip=x.first.second;
//cout<<i<<" "<<tip<<" zzz\n";
if(tip==0)
{
for(auto x:unde[i])
upd(1,1,timer,x,depth[i]);
int cap=i;
while(cap!=1 && n-siz[cap]+1>=siz[i])
cap = parent[cap];
rez[siz[i]] = max(rez[siz[i]], qry(1,1,timer,tin[cap],tout[cap]).abc+1);
}
else
{
rez[n-siz[i]+1] = max(rez[n-siz[i]+1], qry(1,1,timer,tin[i],tout[i]).a-depth[i]+1);
}
}
for(int i=n-1;i>0;i--)
rez[i] = max(rez[i], rez[i+1]);
for(int i=1;i<=n;i++)
{
if(i%2==1)
{
cout<<1<<"\n";
}
else
{
cout<<rez[i/2]<<"\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9820 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
9820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9820 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
9820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9820 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
9820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
