Pagini recente » Cod sursa (job #3176050) | Cod sursa (job #3144624) | Cod sursa (job #2979354) | Cod sursa (job #3275865) | Cod sursa (job #3243132)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
int dist[1005], v[1005], sum[1005], nr;
vector<int> x[1005];
void DFS(int a, int d)
{int max1=-1, ok=0;
sum[a]=dist[a]=0;
vector<int>:: iterator I;
for(I=x[a].begin();I<x[a].end();I++)
if(dist[*I]==-1)
{DFS(*I, d);
if(dist[*I]+1>max1)max1=dist[*I]+1;
if(dist[*I]+1>=d || (a==1 && dist[*I]>0 && sum[*I]!=0))ok=1;
sum[a]+=sum[*I];
}
if(ok)
{sum[a]++;
v[++nr]=a;
dist[a]=-(d+1);
}
else dist[a]=max1+1;
}
int main()
{ int n, k, a, b, st, dr, mij, sol;
fin>>n>>k;
for(int i=1;i<n;i++)
{fin>>a>>b;
x[a].push_back(b);
x[b].push_back(a);
}
if(k>=n)
{fout<<"0\n";
for(int i=1;i<=n;i++)
fout<<i<<" ";
}
else
{st=1, dr=sol=n;
while(st<=dr)
{mij=(st+dr)/2;
for(int i=1;i<=n;i++)
dist[i]=-1;
nr=0;
DFS(1, mij);
if(sum[1]<=k)sol=mij, dr=mij-1;
else st=mij+1;
}
nr=0;
for(int i=1;i<=n;i++)
dist[i]=-1;
DFS(1, sol);
for(int i=1;i<=n && nr<k;i++)
if(dist[i]!=0)v[++nr]=i;
sort(v+1, v+1+nr);
fout<<sol<<"\n";
for(int i=1;i<=nr;i++)
fout<<v[i]<<" ";
}
return 0;
}