#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
const int nax = 2e5 + 5;
int n;
vi adj[nax];
int sz[20][nax], mark[nax], dis[20][nax], ans[nax];
struct node
{
int maxi = 0;
int maxi2 = 0;
int sum = 0;
int lazy1 = 0, lazy2 = 0;
};
node bss;
vector<node> st;
vi nodes[nax];
void mx(int p, int val)
{
if(st[p].maxi <= val)
{
st[p].maxi2 = st[p].maxi;
st[p].maxi = val;
}
else if(st[p].maxi2 < val)
{
st[p].maxi2 = val;
}
st[p].sum = max(st[p].sum, st[p].maxi + st[p].maxi2);
}
void mxlz(int p, int val)
{
if(st[p].lazy1 <= val)
{
st[p].lazy2 = st[p].lazy1;
st[p].lazy1 = val;
}
else if(st[p].lazy2 < val)
{
st[p].lazy2 = val;
}
}
void propagate(int p, int l, int r)
{
if(st[p].lazy1 != 0)
{
if(l != r)
{
mxlz(2 * p, st[p].lazy1);
mxlz(2 * p, st[p].lazy2);
mxlz(2 * p + 1, st[p].lazy1);
mxlz(2 * p + 1, st[p].lazy2);
}
mx(p, st[p].lazy1);
mx(p, st[p].lazy2);
st[p].lazy1 = st[p].lazy2 = 0;
}
}
int query(int p, int l, int r, int i, int j)
{
propagate(p, l, r);
if(i > j)
return 0;
if(l >= i && r <= j)
return st[p].sum;
int m = (l + r)/2;
return max(query(2 * p, l, m, i, min(j, m)),
query(2 * p + 1, m + 1, r, max(i, m + 1), j));
}
void update(int p, int l, int r, int i, int j, int val)
{
propagate(p, l, r);
if(i > j)
return ;
if(l >= i && r <= j)
{
mxlz(p, val);
propagate(p, l, r);
return ;
}
int m = (l + r)/2;
update(2 * p, l, m, i, min(j, m), val);
update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
st[p].sum = max(st[2 * p].sum, st[2 * p + 1].sum);
}
int getsz(int x, int d, int cur, int p = -1)
{
sz[d][x] = 1;
dis[d][x] = cur ;
for(auto e: adj[x])
{
if(mark[e] || (e == p))
continue;
sz[d][x] += getsz(e, d, cur + 1, x);
}
return sz[d][x];
}
int get_centroid(int x, int d, int s, int p = -1)
{
for(auto e: adj[x])
{
if(mark[e] || (e == p))
continue;
if(sz[d][e] > s/2)
return get_centroid(e, d, s, x);
}
return x;
}
int centroid(int x, int d = 0)
{
x = get_centroid(x, d, getsz(x, d, 0));
getsz(x, d, 0);
nodes[x].pb(x);
mark[x] = 1;
vi C;
for(auto e: adj[x])
{
if(mark[e])
continue;
int c = centroid(e, d + 1);
C.pb(c);
}
int k = 1;
while(k < sz[d][x] + 1)
k = (k << 1);
st.assign(2 * k + 1, bss);
for(auto c: C)
{
vector<pii> v;
for(auto e: nodes[c])
{
nodes[x].pb(e);
v.pb({dis[d][e], sz[d][e]});
//cout << '\t' << x << ' ' << e << ' ' << dis[d][e] << ' ' << sz[d][e] << '\n';
}
nodes[c].clear();
sort(all(v));
reverse(all(v));
int prev = 0;
for(auto e: v)
{
if(e.ss <= prev)
continue;
update(1, 0, k - 1, prev + 1, e.ss, e.ff );
//if(x == 3 && e.ss >= 3)
/// cout << "\t\t" << e.ff << '\n';
prev = e.ss;
//cout << '\t'<< x << ' ' << e.ff << ' ' << e.ss << '\n';
}
}
for(int i = 1; i <= sz[d][x]; i++)
{
ans[i] = max(ans[i], query(1, 0, k - 1, i, sz[d][x]));
//if(x == 2)
//cout << query(1, 0, k - 1, i, sz[d][x]) << " ";
}
//cout << '\n';
//cout << x << endl;
return x;
}
void solve()
{
cin >> n;
for(int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
centroid(1);
for(int i = 1; i <= n; i++)
{
if(i & 1)
cout << 1 << '\n';
else
cout << ans[i/2]+ 1 << '\n';
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
/*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
*/
int tt = 1;
while(tt--)
solve();
}
/*
5
1 2
2 3
4 2
3 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9740 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9716 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9660 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9740 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9716 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9660 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9740 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9716 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9660 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
