#include<bits/stdc++.h>
using namespace std ;
#define MAXN 200007
#define LOG 20
int n ;
vector < int > v[ MAXN ] ;
int comp[ MAXN ] , lvl[ MAXN ] ;
int LCA[ MAXN ][ LOG + 1 ] ;
int st[ MAXN ] , en[ MAXN ] ;
int tp ;
int used[ MAXN ] ;
int total ;
int subtree[ MAXN ] , d[ MAXN ] ;
int ans[ MAXN ] ;
int mxseen[ MAXN ] ;
void from_root ( int vertex , int prv ) {
st[ vertex ] = ++ tp ;
comp[ vertex ] = 1 ;
for ( int i = 1 ; i < LOG ; ++ i ) {
LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
}
for ( auto x : v[ vertex ] ) {
if ( x == prv ) { continue ; }
lvl[ x ] = lvl[ vertex ] + 1 ;
LCA[ x ][ 0 ] = vertex ;
from_root ( x , vertex ) ;
comp[ vertex ] += comp[ x ] ;
}
en[ vertex ] = tp ;
}
void init ( int vertex , int prv ) {
++ total ;
subtree[ vertex ] = 1 ;
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 || x == prv ) { continue ; }
d[ x ] = d[ vertex ] + 1 ;
init ( x , vertex ) ;
subtree[ vertex ] += subtree[ x ] ;
}
}
int get_cen ( int vertex , int prv ) {
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 || x == prv ) { continue ; }
if ( 2 * subtree[ x ] > total ) {
return get_cen ( x , vertex ) ;
}
}
return vertex ;
}
int suff[ MAXN ] ;
int mx_cur[ MAXN ] ;
class Tree {
public :
int tr[ 4 * MAXN ] ;
void init ( int where , int IL , int IR ) {
tr[ where ] = -MAXN ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
}
void update ( int where , int IL , int IR , int pos , int nw ) {
if ( IL == IR ) {
if ( nw < 0 ) { tr[ where ] = -MAXN ; }
else { tr[ where ] = max ( tr[ where ] , nw ) ; }
return ;
}
int mid = ( IL + IR ) / 2 ;
if ( pos <= mid ) {
update ( 2 * where , IL , mid , pos , nw ) ;
}
else {
update ( 2 * where + 1 , mid + 1 , IR , pos , nw ) ;
}
tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
}
int query ( int where , int IL , int IR , int CURL , int CURR ) {
if ( IL > IR || CURL > CURR ) { return -MAXN ; }
if ( IR < CURL || CURR < IL ) { return -MAXN ; }
if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
int mid = ( IL + IR ) / 2 ;
return max ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
}
};
Tree w ;
int get_prv ( int x , int targ ) {
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( lvl[ x ] - ( 1 << i ) >= targ ) {
x = LCA[ x ][ i ] ;
}
}
return x ;
}
void dfs ( int vertex , int prv , int ori ) {
int cnt = 0 , oth = 0 ;
if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
int lst = get_prv ( ori , lvl[ vertex ] + 1 ) ;
cnt = n - comp[ lst ] ;
oth = comp[ ori ] ;
}
else if ( st[ ori ] <= st[ vertex ] && en[ vertex ] <= en[ ori ] ) {
int lst = get_prv ( vertex , lvl[ ori ] + 1 ) ;
cnt = comp[ vertex ] ;
oth = n - comp[ lst ] ;
}
else {
cnt = comp[ vertex ] ;
oth = comp[ ori ] ;
}
ans[ cnt ] = max ( ans[ cnt ] , w.query ( 1 , 1 , n , cnt , n ) + d[ vertex ] + 1 ) ;
ans[ min ( cnt , oth ) ] = max ( ans[ min ( cnt , oth ) ] , d[ vertex ] + 1 ) ;
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 || x == prv ) { continue ; }
dfs ( x , vertex , ori ) ;
}
}
void upd ( int vertex , int prv , int ori ) {
int cnt = 0 ;
if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
cnt = n - comp[ vertex ] + 1 ;
}
else { cnt = comp[ vertex ] ; }
w.update ( 1 , 1 , n , cnt , d[ vertex ] ) ;
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 || x == prv ) { continue ; }
upd ( x , vertex , ori ) ;
}
}
void rem ( int vertex , int prv , int ori ) {
int cnt = 0 ;
if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
cnt = n - comp[ vertex ] + 1 ;
}
else { cnt = comp[ vertex ] ; }
w.update ( 1 , 1 , n , cnt , -1 ) ;
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 || x == prv ) { continue ; }
rem ( x , vertex , ori ) ;
}
}
void decompose ( int vertex ) {
total = 0 , d[ vertex ] = 0 ;
init ( vertex , -1 ) ;
vertex = get_cen ( vertex , -1 ) ;
total = 0 , d[ vertex ] = 0 ;
init ( vertex , -1 ) ;
used[ vertex ] = 1 ;
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 ) { continue ; }
dfs ( x , vertex , vertex ) ;
upd ( x , vertex , vertex ) ;
}
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 ) { continue ; }
rem ( x , vertex , vertex ) ;
}
int sz = v[ vertex ].size ( ) ;
for ( int i = sz - 1 ; i >= 0 ; -- i ) {
int x = v[ vertex ][ i ] ;
dfs ( x , vertex , vertex ) ;
upd ( x , vertex , vertex ) ;
}
for ( int i = sz - 1 ; i >= 0 ; -- i ) {
int x = v[ vertex ][ i ] ;
if ( used[ x ] == 1 ) { continue ; }
rem ( x , vertex , vertex ) ;
}
for ( auto x : v[ vertex ] ) {
if ( used[ x ] == 1 ) { continue ; }
decompose ( x ) ;
}
}
void input ( ) {
cin >> n ;
for ( int i = 1 ; i < n ; ++ i ) {
int x , y ;
cin >> x >> y ;
v[ x ].push_back ( y ) ;
v[ y ].push_back ( x ) ;
}
from_root ( 1 , -1 ) ;
}
void solve ( ) {
w.init ( 1 , 1 , n ) ;
decompose ( 1 ) ;
for ( int i = n / 2 ; i >= 1 ; -- i ) {
ans[ i ] = max ( ans[ i ] , ans[ i + 1 ] ) ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
if ( ( i % 2 ) == 1 ) { cout << "1\n" ; }
else { cout << ans[ i / 2 ] << "\n" ; }
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ;
// cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
