Pagini recente » Cod sursa (job #814185) | Cod sursa (job #406142) | Cod sursa (job #309322) | Cod sursa (job #2924686) | Cod sursa (job #1607276)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("salvare.in");
ofstream out("salvare.out");
const int N = 1010;
int n, k;
int dp[N];
bool vis[N];
vector < int > adj[N];
int cnt, dmax;
void dfs(int x, int p) {
for(auto i : adj[x]) if(i != p) {
dfs(i, x);
dp[x] = max(dp[x], dp[i] + 1);
}
if(dp[x] == dmax) {
dp[x] = 0;
vis[x] = 1;
cnt++;
}
}
void get_min_dist() {
int lo, hi, med;
lo = 1;
hi = n;
while(lo <= hi) {
med = (lo + hi) >> 1;
cnt = 0; dmax = med;
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
dfs(1, 0);
if(cnt <= k) {
hi = med - 1;
}
else {
lo = med + 1;
}
}
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
dmax = hi + 1;
dfs(1, 0);
}
int main() {
int i, u, v;
in >> n >> k;
for(i = 1; i < n; i++) {
in >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
get_min_dist();
out << dmax << '\n';
for(i = 1; i <= n; i++) {
if(vis[i]) {
out << i << ' ';
}
}
return 0;
}