#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
const int INF = 1e8;
int ans[MAX_N + 1];
struct AIB {
int n;
vector<int> aib, changes;
void resize( int _n ) {
n = _n;
aib.clear();
aib.resize( n + 1 );
for ( int i = 0; i <= n; i++ )
aib[i] = -INF;
changes.clear();
}
void clear() {
for ( int i: changes )
aib[i] = -INF;
changes.clear();
}
void update( int i, int x ) {
changes.push_back( i );
while ( i <= n ) {
aib[i] = max( aib[i], x );
i += (i & -i);
}
}
int query( int i ) {
int x = -INF;
while ( i > 0 ) {
x = max( aib[i], x );
i -= (i & -i);
}
return x;
}
};
struct Tree {
struct edge {
int u, v, c;
int other( int w ) {
return u ^ v ^ w;
}
};
int n;
vector<edge> edges;
vector<vector<int>> adj;
vector<bool> isCentroid;
vector<int> depth, timeIn, timeOut, subtreeSize, centroidSubtreeSize, centroidDist;
vector<vector<int>> parent;
AIB verticesDist;
void resize( int _size ) {
n = _size;
edges.clear();
adj.clear();
adj.resize( n + 1 );
depth.clear();
depth.resize( n + 1 );
isCentroid.clear();
isCentroid.resize( n + 1 );
timeIn.clear();
timeIn.resize( n + 1 );
timeOut.clear();
timeOut.resize( n + 1 );
subtreeSize.clear();
subtreeSize.resize( n + 1 );;
centroidSubtreeSize.clear();
centroidSubtreeSize.resize( n + 1 );
centroidDist.clear();
centroidDist.resize( n + 1 );
parent.clear();
parent.resize( (int)log2( n ) + 1 );
for ( int i = 0; i <= log2( n ); i++ )
parent[i].resize( n + 1 );
verticesDist.resize( n );
}
void add_edge( int u, int v, int c ) {
adj[u].push_back( edges.size() );
adj[v].push_back( edges.size() );
edges.push_back( { u, v, c } );
}
int timee;
void dfs( int u, int p ) {
parent[0][u] = p;
subtreeSize[u] = 1;
timeIn[u] = ++timee;
for ( int e: adj[u] ) {
int v = edges[e].other( u ), c = edges[e].c;
if ( v == p )
continue;
depth[v] = depth[u] + c;
dfs( v, u );
subtreeSize[u] += subtreeSize[v];
}
timeOut[u] = timee;
}
void init( int root ) {
timee = 0;
dfs( root, 0 );
for ( int l = 1; l <= log2( n ); l++ ) {
for ( int v = 1; v <= n; v++ )
parent[l][v] = parent[l - 1][parent[l - 1][v]];
}
}
int kthAncestor( int v, int k ) {
for ( int l = log2( n ); l >= 0; l-- ) {
if ( k >= (1 << l) ) {
v = parent[l][v];
k -= (1 << l);
}
}
return v;
}
int lca( int u, int v ) {
if ( depth[u] > depth[v] )
swap( u, v );
v = kthAncestor( v, depth[v] - depth[u] );
if ( u == v )
return v;
for ( int l = log2( n ); l >= 0; l-- ) {
if ( parent[l][u] != parent[l][v] ) {
u = parent[l][u];
v = parent[l][v];
}
}
return parent[0][v];
}
int dist( int u, int v ) {
int l = lca( u, v );
return depth[u] + depth[v] - 2 * depth[l];
}
int orientedChild( int v, int u ) {
return kthAncestor( u, depth[u] - depth[v] - 1 );
}
bool inSubtree( int r, int v ) {
return (timeIn[r] <= timeIn[v]) && (timeOut[v] <= timeOut[r]);
}
int orientedSubtreeSize( int r, int v ) {
if ( inSubtree( v, r ) ) {
int u = orientedChild( v, r );
return n - subtreeSize[u];
}
return subtreeSize[v];
}
void calcCentroidSizes( int u, int p ) {
centroidSubtreeSize[u] = 1;
for ( int e: adj[u] ) {
int v = edges[e].other( u );
if ( v == p || isCentroid[v] )
continue;
calcCentroidSizes( v, u );
centroidSubtreeSize[u] += centroidSubtreeSize[v];
}
}
int sizee, centroid;
void findCentroid( int u, int p ) {
int maxSize = sizee - centroidSubtreeSize[u];
for ( int e: adj[u] ) {
int v = edges[e].other( u );
if ( v == p || isCentroid[v] )
continue;
findCentroid( v, u );
maxSize = max( maxSize, centroidSubtreeSize[v] );
}
if ( maxSize <= sizee / 2 )
centroid = u;
}
vector<int> vertices;
void compute( int u, int p ) {
vertices.push_back( u );
centroidDist[u] = centroidDist[p] + 1;
for ( int e: adj[u] ) {
int v = edges[e].other( u );
if ( v == p || isCentroid[v] )
continue;
compute( v, u );
}
}
void decomp( int r ) {
calcCentroidSizes( r, 0 );
sizee = centroidSubtreeSize[r];
findCentroid( r, 0 );
int c = centroid;
verticesDist.clear();
centroidDist[c] = 0;
for ( int e: adj[c] ) {
int v = edges[e].other( c );
if ( isCentroid[v] )
continue;
vertices.clear();
compute( v, c );
for ( int u: vertices ) {
int d = dist( u, c ) + 1, x = orientedSubtreeSize( u, c ), y = orientedSubtreeSize( c, u );
ans[min( x, y ) * 2] = max( ans[min( x, y ) * 2], d );
}
for ( int u: vertices )
ans[orientedSubtreeSize( c, u ) * 2] = max( ans[orientedSubtreeSize( c, u ) * 2], centroidDist[u] + verticesDist.query( n + 1 - orientedSubtreeSize( c, u ) ) + 1 );
for ( int u: vertices )
verticesDist.update( n + 1 - orientedSubtreeSize( c, u ), centroidDist[u] );
}
isCentroid[c] = true;
for ( int e: adj[c] ) {
int v = edges[e].other( c );
if ( !isCentroid[v] )
decomp( v );
}
}
};
Tree islands;
int main() {
int n;
cin >> n;
islands.resize( n );
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
islands.add_edge( u, v, 1 );
}
islands.init( 1 );
for ( int i = 1; i <= n; i++ )
ans[i] = 1;
islands.decomp( 1 );
for ( int i = n - 2; i >= 1; i-- )
ans[i] = max( ans[i], ans[i + 2] );
for ( int i = 1; i <= n; i++ )
cout << ans[i] << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
