#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int N = 2e5 + 1;
const int inf = 1e15;
int n;
struct SegTree{
int T[N * 4];
SegTree(){
for ( int i = 0; i < N * 4; i++ ){
T[i] = -inf;
}
}
void upd(int v, int l, int r, int pos, int vl){
if ( l == r ){
T[v] = vl;
return;
}
int md = (l + r) >> 1;
if ( pos <= md ){
upd(v * 2, l, md, pos, vl);
} else{
upd(v * 2 + 1, md + 1, r, pos, vl);
}
T[v] = max(T[v * 2], T[v * 2 + 1]);
}
void upd(int pos, int vl){
upd(1, 0, n, pos, vl);
}
int get(int v, int l, int r, int tl, int tr){
if ( l > tr or r < tl ){
return -inf;
}
if ( tl <= l && tr >= r ){
return T[v];
}
int md = (l + r) >> 1;
return max(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
}
int get(int l, int r){
return get(1, 0, n, l, r);
}
} seg;
vector <int> G[N];
int us[N], sub[N];
void dfs(int u, int p){
sub[u] = 1;
for ( auto &v: G[u] ){
if ( v != p && !us[v] ){
dfs(v, u);
sub[u] += sub[v];
}
}
}
int find(int u, int p, int des){
for ( auto &v: G[u] ){
if ( v != p && !us[v] ){
if ( sub[v] >= des / 2 ){
return find(v, u, des);
}
}
}
return u;
}
vector <vector<ar<int,2>>> t;
int sz;
int ans[N * 2];
void dfs2(int u, int p, int d){
chmax(ans[min(sz, sub[u]) * 2], d + 1); // with root
t.back().pb({sub[u], d});
for ( auto &v: G[u] ){
if ( v != p && !us[v] ){
dfs2(v, u, d + 1);
}
}
}
void decompose(int rt){
dfs(rt, -1);
int u = find(rt, -1, sub[rt]);
dfs(u, -1);
us[u] = true;
for ( auto &v: G[u] ){
if ( us[v] ) continue;
sz = sub[u] - sub[v];
t.pb({});
dfs2(v, u, 1);
}
{ // prefix
for ( auto &x: t ){
for ( auto &[s, d]: x ){
chmax(ans[s * 2], seg.get(s, n) + d + 1);
}
for ( auto &[s, d]: x ){
seg.upd(s, d);
}
}
for ( auto &x: t ){
for ( auto &[s, d]: x ){
seg.upd(s, -inf);
}
}
} // suffix
{
reverse(all(t));
for ( auto &x: t ){
for ( auto &[s, d]: x ){
chmax(ans[s * 2], seg.get(s, n) + d + 1);
}
for ( auto &[s, d]: x ){
seg.upd(s, d);
}
}
for ( auto &x: t ){
for ( auto &[s, d]: x ){
seg.upd(s, -inf);
}
}
} t.clear();
for ( auto &v: G[u] ){
if ( !us[v] ){
decompose(v);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// 1 - indexed
cin >> n;
for ( int i = 1; i < n; i++ ){
int u, v; cin >> u >> v;
G[u].pb(v), G[v].pb(u);
}
decompose(1);
for ( int i = n - (n & 1); i > 0; i -= 2 ){
chmax(ans[i], ans[i + 2]);
}
for ( int i = 1; i <= n; i++ ){
cout << (i & 1 ? 1LL : max(ans[i], 1LL)) << ln;
}
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15448 KB |
Output is correct |
| 2 |
Correct |
2 ms |
15704 KB |
Output is correct |
| 3 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15452 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15448 KB |
Output is correct |
| 2 |
Correct |
2 ms |
15704 KB |
Output is correct |
| 3 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15452 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15448 KB |
Output is correct |
| 2 |
Correct |
2 ms |
15704 KB |
Output is correct |
| 3 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15452 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
