Pagini recente » Cod sursa (job #895071) | Cod sursa (job #2040049) | Cod sursa (job #1603571) | Cod sursa (job #2100223) | Cod sursa (job #1998818)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
using Tree = vector<vector<int>>;
vector<int> GetNodes(const Tree &t, int max_time)
{
vector<int> nodes;
queue<int> q;
vector<int> max_dist(t.size(), 0);
vector<bool> visited(t.size(), false);
for (size_t i = 0; i < t.size(); ++i) {
if (t[i].size() == 1) {
q.push(i);
}
}
while (!q.empty()) {
int node = q.front();
q.pop();
if (visited[node]) {
continue;
}
visited[node] = true;
if (max_dist[node] == max_time) {
nodes.push_back(node);
max_dist[node] = 0;
}
for (int next : t[node]) {
if (!visited[next]) {
max_dist[next] = max(max_dist[next], max_dist[node] + 1);
q.push(next);
}
}
}
return nodes;
}
int main()
{
ifstream fin("salvare.in");
ofstream fout("salvare.out");
int nodes, k;
fin >> nodes >> k;
Tree tree(nodes);
for (int i = 1; i < nodes; ++i) {
int x, y;
fin >> x >> y;
tree[x - 1].push_back(y - 1);
tree[y - 1].push_back(x - 1);
}
int res_time = 0;
int power = (1 << 25);
while (power > 0) {
if ((int)GetNodes(tree, res_time + power).size() > k) {
res_time += power;
}
power >>= 1;
}
++res_time;
auto res_nodes = GetNodes(tree, res_time);
fout << res_time << "\n";
for (int node : res_nodes) {
fout << node + 1 << " ";
}
return 0;
}