Pagini recente » Cod sursa (job #185561) | Cod sursa (job #717914) | Cod sursa (job #1105181) | Cod sursa (job #1792859) | Cod sursa (job #2542574)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
const int Nmax = 1001;
const int oo = 2e9;
int n, k, lgsol;
int dist[Nmax], sol[Nmax];
vector <int> L[Nmax];
void Dfs(int tata, int nod, int &salvare, int lg)
{
int minim = oo;
dist[nod] = 0;
for(auto i : L[nod])
if(i != tata)
{
Dfs(nod, i, salvare, lg);
dist[nod] = max(dist[nod], dist[i] + 1);
minim = min(minim, dist[i] + 1);
}
if(dist[nod] == lg)
{
dist[nod] = -lg-1;
salvare--;
return ;
}
if(minim < 0 && -minim - 1 >= dist[nod])
dist[nod] = minim;
}
int main()
{
fin >> n >> k;
int x, y;
for(int i = 1; i < n; i++)
{
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
int salvare;
int l, r, m, p;
l = 0; r = Nmax - 1;
while(l <= r)
{
m = (l + r) / 2;
Dfs(0, 1, salvare = k, m);
if(dist[1] >= 0)
salvare--;
if(salvare >= 0)
{
r = m - 1;
p = m;
lgsol = 0;
if(dist[1] >= 0)
sol[++lgsol] = 1;
for(int i = 1; i <= n; i++)
if(dist[i] == -m-1)sol[++lgsol] = i;
}
else l = m + 1;
}
fout << p << "\n";
for(int i = 1; i <= lgsol; i++)
fout << sol[i] << " ";
fin.close();
fout.close();
return 0;
}