Pagini recente » Cod sursa (job #862004) | Cod sursa (job #493881) | Cod sursa (job #2440736) | Cod sursa (job #2197451) | Cod sursa (job #1473306)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin( "salvare.in" ); ofstream fout( "salvare.out" );
const int nmax = 1000;
int n, k;
bool keke[ nmax + 1 ], safe[ nmax + 1 ];
vector< int > ans, pct;
vector< int > g[ nmax + 1 ], noduri[ nmax + 1 ];
int tata[ nmax + 1 ];
void dfs( int nod, int nivel ) {
noduri[ nivel ].push_back( nod );
for( vector< int >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
if ( *it != tata[ nod ] ) {
tata[ *it ] = nod;
dfs( *it, nivel + 1 );
}
}
}
void bfs( int nod, int lg, int sursa ) {
safe[ nod ] = 1;
if ( lg == 0 ) return ;
for( vector< int >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
if ( *it != sursa ) {
bfs( *it, lg - 1, nod );
}
}
}
void verifica_si_salveaza( int nod, int lg ) {
int w = nod, aux = lg;
if ( safe[ nod ] == 1 ) return ;
while ( w != 1 && aux > 0 ) {
w = tata[ w ];
-- aux;
}
if ( keke[ w ] == 0 ) {
keke[ w ] = 1;
bfs( w, lg, 0 );
pct.push_back( w );
}
}
bool check( int x ) {
for( int i = 1; i <= n; ++ i ) {
keke[ i ] = safe[ i ] = 0;
}
pct.clear();
for( int i = n; i >= 0; -- i ) {
for( vector< int >::iterator j = noduri[ i ].begin(); j != noduri[ i ].end(); ++ j ) {
verifica_si_salveaza( *j, x );
}
}
for( int i = 1; i <= n; ++ i ) {
if ( safe[ i ] == 0 ) {
return 0;
}
}
if ( ( int )pct.size() > k ) {
return 0;
}
for( int i = 1; i <= n && ( int )pct.size() < k; ++ i ) {
if ( keke[ i ] == 0 ) {
pct.push_back( i );
}
}
return 1;
}
int bs() {
int n2, sol = n;
for( n2 = 1; (n2 << 1) <= n; n2 <<= 1 ) {
}
for( int step = n2; step > 0; step >>= 1 ) {
if ( sol - step >= 0 && check( sol - step ) ) {
sol -= step;
ans = pct;
}
}
return sol;
}
int main() {
fin >> n >> k;
for( int i = 1; i < n; ++ i ) {
int x, y;
fin >> x >> y;
g[ x ].push_back( y ); g[ y ].push_back( x );
}
tata[ 1 ] = 0;
dfs( 1, 0 );
fout << bs() << "\n";
sort( ans.begin(), ans.end() );
for( vector< int >::iterator it = ans.begin(); it != ans.end(); ++ it ) {
fout << *it << " ";
}
fout << "\n";
fin.close();
fout.close();
return 0;
}