bzoj 1086 树分块

将树分成一些块，做法见vfleaking博客。

 /**************************************************************

     Problem: 1086

     User: idy002

     Language: C++

     Result: Accepted

     Time:20 ms

     Memory:852 kb

 ****************************************************************/

 #include <cstdio>

 #include <vector>

 #define maxn 1010

 using namespace std;

 int n, b;

 int mccno[maxn];

 int cent[maxn], mtot;

 vector<int> mcc[maxn];

 vector<int> g[maxn], remain[maxn];

 void dfs( int u, int fa ) {

     for( int t=; t<g[u].size(); t++ ) {

         int v = g[u][t];

         if( v==fa ) continue;

         dfs(v,u);

         while( remain[v].size() ) {

             remain[u].push_back( remain[v].back() );

             remain[v].pop_back();

         }

         if( remain[u].size() >= b ) {

             mtot++;

             cent[mtot] = u;

             while( !remain[u].empty() ) {

                 mccno[ remain[u].back() ] = mtot;

                 mcc[ mtot ].push_back( remain[u].back() );

                 remain[u].pop_back();

             }

         }

     }

     remain[u].push_back( u );

 }

 int main() {

     scanf( "%d%d", &n, &b );

     for( int i=,u,v; i<n; i++ ) {

         scanf( "%d%d", &u, &v );

         g[u].push_back(v);

         g[v].push_back(u);

     }

     dfs(,);

     while( !remain[].empty() ) {

         mccno[ remain[].back() ] = mtot;

         mcc[ mtot ].push_back( remain[].back() );

         remain[].pop_back();

     }

     printf( "%d\n", mtot );

     for( int i=; i<=n; i++ )

         printf( "%d ", mccno[i] );

     printf( "\n" );

     for( int i=; i<=mtot; i++ )

         printf( "%d ", cent[i] );

     printf( "\n" );

 }