Pagini recente » Cod sursa (job #2841885) | Cod sursa (job #1528174) | Cod sursa (job #2762968) | Cod sursa (job #1891269) | Cod sursa (job #1571053)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1010;
int N, K;
int nodes[NMAX];
vector<int> G[NMAX];
int DFS(int node, int from, int curr, int max) {
int ret = 0;
if (curr > max + 1 || curr == 1)
nodes[node] = ret = 1;
for (int next : G[node]) {
if (next == from)
continue;
if (curr > max + 1)
ret += DFS(next, node, 2, max);
else
ret += DFS(next, node, curr + 1, max);
}
return ret;
}
int MaxDepth(int node, int from, int curr) {
if (G[node].size() == 1)
return curr;
int ret = -1;
for (int next : G[node]) {
if (node != from)
continue;
ret = max(ret, MaxDepth(next, node, curr + 1));
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
assert(freopen("salvare.in", "r", stdin) != NULL);
assert(freopen("salvare.out", "w", stdout) != NULL);
assert(freopen("debug.err", "w", stderr) != NULL);
#endif
int i, j, x, y;
cin >> N >> K;
for (i = 0; i < N - 1; ++i) {
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
int root = 1, depth = MaxDepth(1, -1, 1);
for (i = 2; i <= N; ++i) {
int curr = MaxDepth(i, -1, 1);
if (curr < depth) {
depth = curr;
root = i;
}
}
int res = (1 << 10) - 1;
for (int bit = (1 << 9); bit; bit >>= 1)
if (DFS(root, -1, 1, res - bit) <= K)
res -= bit;
memset(nodes, 0, sizeof(nodes));
cout << res << '\n';
int num = K - DFS(root, -1, 1, res);
for (i = 1; i <= N; ++i)
if (nodes[i] == 1)
cout << i << ' ';
else if (num) {
--num;
cout << i << ' ';
}
cout << '\n';
return 0;
}