Pagini recente » Cod sursa (job #2678987) | Cod sursa (job #2941346) | Cod sursa (job #2961361) | Cod sursa (job #1252403) | Cod sursa (job #2589365)
#include <fstream>
#include <vector>
#include <algorithm>
#define N 1001
using namespace std;
ifstream f ( "salvare.in" );
ofstream g ( "salvare.out" );
vector < int > graph[N];
int d[N], pct[N], l, k, n;
bool viz[N];
void dfs ( int node, int tmp ){
viz[node] = 1;
for ( int i = 0; i < graph[node].size ( ); i++ ){
int new_node = graph[node][i];
if ( viz[new_node] == 0 ){
dfs ( new_node, tmp );
d[node] = max ( d[node], d[new_node] + 1 );
if ( d[node] == tmp ){
pct[++l] = node;
d[node] = -tmp - 1;
}
}
}
}
bool verif ( int tmp ){
l = 0;
for ( int i = 1; i <= n; i++ ){
d[i] = 0;
viz[i] = 0;
}
dfs ( 1, tmp );
if ( d[1] > 0 )
pct[++l] = 1;
if ( l == k )
return 1;
return 1;
}
int main()
{ int st, dr, i, x, y, sol;
f >> n >> k;
for ( i = 1; i <= n - 1; i++ ){
f >> x >> y;
graph[x].push_back ( y );
graph[y].push_back ( x );
}
st = 1, dr = n;
while ( st <= dr ){
int mid = ( st + dr ) >> 1;
if ( verif ( mid ) == 1 ){
sol = mid;
dr = mid - 1;
}
else
st = mid + 1;
}
g << sol << '\n';
sort ( pct + 1, pct + k + 1 );
for ( i = 1; i <= k; i++ )
g << pct[i] << ' ';
return 0;
}