Pagini recente » Cod sursa (job #1634517) | Cod sursa (job #749008) | Cod sursa (job #1964874) | Cod sursa (job #1003988) | Cod sursa (job #2592906)
#include <fstream>
#include <cstdlib>
#include <vector>
using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
vector <int> g[1001],rez,sol;
int d[1001];
int n,k,st,dr,tmax,dist,x,y;
void dfs(int nod, int tata)
{
int Min=2000000000;
for(int i=0;i<g[nod].size();i++)
{
int nou=g[nod][i];
if(nou!=tata)
{
dfs(nou,nod);
d[nod]=max(d[nod],d[nou]+1);
Min=min(Min,d[nou]+1);
}
}
if(d[nod]==dist)
{
rez.push_back(nod);
d[nod]=-dist-1;
}
if(Min<0&&-Min>d[nod])
d[nod]=Min;
else if(Min>0&&Min<d[nod])
d[nod]=Min;
}
int main()
{
fin>>n>>k;
for(int i=1;i<n;i++)
{
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
st=1,dr=n;
while(st<=dr)
{
int mid=(st+dr)/2;
for(int i=1;i<n;i++)
d[i]=0;
rez.clear();
dist=mid;
dfs(1,0);
if(d[1]>0)
rez.push_back(1);
if(rez.size()<=k)
{
sol.clear();
for(int i=0;i<rez.size();i++)
sol.push_back(rez[i]);
tmax=mid;
dr=mid-1;
}
else
st=mid+1;
}
fout<<tmax<<'\n';
for(int i=0;i<sol.size();i++)
fout<<sol[i]<<' ';
return 0;
}