Pagini recente » Cod sursa (job #2118807) | Cod sursa (job #151200) | Cod sursa (job #1159434) | Cod sursa (job #1622256) | Cod sursa (job #2825458)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
vector <int> v[1005];
int sir[1005], n, k, w[1005], copie[1005], rasp[1005], dph[1005], num, nr, ans[1005];
void dfs(int nod, int l)
{
int maxx=-1, minn=1000;
for(int i=0; i<v[nod].size(); i++)
if(w[v[nod][i]]==0)
{
w[v[nod][i]]=1;
dfs(v[nod][i], l);
maxx=max(maxx, dph[v[nod][i]]);
minn=min(minn, dph[v[nod][i]]+1);
}
dph[nod]=maxx+1;
if(dph[nod]==l)
{
num++;
rasp[num]=nod;
dph[nod]=-l-1;
}
else
if(minn<0 && -minn>dph[nod]) dph[nod]=minn;
}
int verif(int l)
{
num=0; w[1]=1;
dfs(1, l);
if(dph[1]>0)
{
num++; rasp[num]=1;
}
for(int i=1; i<=n; i++ ) w[i]=0, dph[i]=0;
if(num<=k) return 1;
return 0;
}
int cond(int a, int b)
{
return v[a].size()>v[b].size();
}
void copyy()
{
nr=num;
for(int i=1; i<=nr; i++)
ans[i]=rasp[i];
}
int main()
{
fin >> n >> k;
for(int i=1; i<n; i++)
{
int x, y; fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
int st=1, dr=n, ok;
while(st<=dr)
{
int mij=(st+dr)/2;
if(verif(mij))
{
copyy();
ok=mij;
dr=mij-1;
}
else st=mij+1;
}
fout << ok << "\n";
sort(ans+1, ans+nr+1);
for(int i=1; i<=nr; i++)
fout << ans[i] << " ";
return 0;
}