Pagini recente » Cod sursa (job #2990704) | Borderou de evaluare (job #3295890) | Cod sursa (job #2522135) | Cod sursa (job #3279091) | Cod sursa (job #3300395)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#define nmax 1005
using namespace std;
ifstream cin("salvare.in");
ofstream cout("salvare.out");
int n,k,x,y,d[nmax];
bool viz[nmax],in[nmax];
vector<int>v[nmax],sol;
void dfs(int nod,int dist){
viz[nod]=1;
d[nod]=1;
int mini=nmax,maxi=0,val=0;
for(auto i:v[nod])
if(!viz[i]){
dfs(i,dist);
maxi=max(maxi,d[i]);
mini=min(mini,d[i]);
}
if(mini==nmax)
return ;
if(mini>=0)
val=mini+maxi;
else
val=dist+mini+maxi+1;
if(maxi==dist){
sol.push_back(nod);
d[nod]=-dist;
}else if(val<=dist||maxi<0)
d[nod]=mini+1;
else
d[nod]=maxi+1;
}
int verif(int dist){
sol.clear();
memset(viz,0,sizeof(viz));
dfs(1,dist);
return sol.size();
}
int main()
{
cin>>n>>k;
for(int i=1;i<n;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
if(k==n){
cout<<"0\n";
for(int i=1;i<=n;i++)
cout<<i<<" ";
return 0;
}
int r=n,st=1,dr=n;
while(st<=dr){
int mid=(st+dr)/2;
if(verif(mid)<=k)
r=mid,dr=mid-1;
else
st=mid+1;
}
cout<<r<<'\n';
verif(r);
r=sol.size();
for(auto i:sol)
in[i]=1;
for(int i=1;i<=n&&r<k;i++)
if(!in[i]){
r++;
sol.push_back(i);
}
sort(sol.begin(),sol.end());
for(auto i:sol)
cout<<i<<" ";
return 0;
}