Pagini recente » Cod sursa (job #1442102) | Cod sursa (job #627455) | Cod sursa (job #67674) | Cod sursa (job #2965111) | Cod sursa (job #3243112)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
int dist[10005], v[10005], sum[10005], nr;
vector<int> x[10005];
int DFS(int a, int d)
{int max1=0, max2=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)max2=max1, max1=dist[*I]+1;
else if(dist[*I]+1>max2)max2=dist[*I]+1;
sum[a]+=sum[*I];
}
if(max1+max2>d)
{sum[a]++;
v[++nr]=a;
dist[a]=0;
}
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;
}