Pagini recente » Cod sursa (job #2373479) | Cod sursa (job #3002632) | Cod sursa (job #1204197) | Cod sursa (job #1780400) | Cod sursa (job #2418269)
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
ifstream in("salvare.in");
ofstream out("salvare.out");
priority_queue<pii, vector<pii>, greater<pii> > h;
const int N = 1e4+5;
vector<int> v[N];
int cost[N],gr[N],dist[N];
bool viz[N];
int main()
{
int n,k;
in >> n >> k;
for (int i = 1; i<n; i++)
{
int x,y;
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
gr[x]++;
gr[y]++;
}
for (int i = 1; i<=n; i++)
{
if (gr[i] == 1)
h.push({1,i});
cost[i] = 1;
}
int elim = 0;
while (!h.empty())
{
int now = h.top().second;
h.pop();
if (!viz[now])
{
elim++;
viz[now] = 1;
if (elim == n-k)
break;
for (auto it: v[now])
if (!viz[it])
{
cost[it]+=cost[now];
gr[it]--;
if (gr[it] == 1)
h.push({cost[it],it});
}
}
}
queue<int> q;
for (int i = 1; i<=n; i++)
if (!viz[i])
{
dist[i] = 1;
q.push(i);
}
while (!q.empty())
{
int now = q.front();
q.pop();
for (auto it: v[now])
if (!dist[it])
{
dist[it] = 1+dist[now];
q.push(it);
}
}
int Max = 0;
for (int i = 1; i<=n; i++)
if (dist[i]-1>Max)
Max = dist[i]-1;
out << Max << "\n";
for (int i = 1; i<=n; i++)
if (!viz[i])
out << i << " ";
}