Pagini recente » Cod sursa (job #3198283) | Cod sursa (job #423696) | Cod sursa (job #1191310) | Cod sursa (job #2093937) | Cod sursa (job #2390034)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
int N, K, V[1005], cnt, f[1005];
vector<int> Sol, edge[1005];
void dfs( int D, int nod ){
f[nod] = 1; bool ok = false;
for( int v : edge[nod] ){
if( f[v] == 0 ){
ok = true;
dfs( D, v );
}
}
if( ok == false ){
V[nod] = D;
}else{
for( int v : edge[nod] )
if( f[v] == 0 )
V[nod] = min( V[nod], V[v] - 1 );
if( V[nod] == 0 )
++cnt, V[nod] = 2 * D;
}
f[nod] = 0;
}
void solve( int D, int nod ){
f[nod] = 1; bool ok = false;
for( int v : edge[nod] ){
if( f[v] == 0 ){
ok = true;
solve( D, v );
}
}
if( ok == false ){
V[nod] = D;
}else{
for( int v : edge[nod] )
if( f[v] == 0 )
V[nod] = min( V[nod], V[v] - 1 );
if( V[nod] == 0 )
Sol.push_back( nod ), V[nod] = 2 * D;
}
f[nod] = 0;
}
int main(){
fin >> N >> K;
for( int i = 1; i < N; ++i ){
int x, y; fin >> x >> y;
edge[x].push_back( y );
edge[y].push_back( x );
}
if( N <= K ){
fout << "0\n";
for( int i = 1; i <= N; i++ )
fout << i << " ";
return 0;
}
int st = 1, dr = N, mid;
while( st <= dr ){
mid = ( st + dr ) >> 1;
cnt = 0;
memset( V, 0x3f3f3f3f, sizeof(V) );
dfs( mid, 1 );
if( cnt <= K )
dr = mid - 1;
else
st = mid + 1;
}
solve( st, 1 );
sort( Sol.begin(), Sol.end() );
fout << st << "\n";
for( int i = 0; i < Sol.size(); i++ )
fout << Sol[i] << " ";
return 0;
}