Pagini recente » Cod sursa (job #2220314) | Cod sursa (job #2665540) | Cod sursa (job #2064740) | Cod sursa (job #135791) | Cod sursa (job #1566744)
#include <bits/stdc++.h>
#define Nmax 1005
#define INF 1000000000
#define pb push_back
using namespace std;
int n,k,x,cnt,dist[Nmax],minn[Nmax];
vector <int> L[Nmax],aux,ans;
inline void Dfs(int nod, int tata)
{
int Node;
for(auto it : L[nod])
{
if(it==tata) continue;
Dfs(it,nod);
if(dist[it]+1 > dist[nod])
{
dist[nod]=dist[it]+1; Node=it;
}
minn[nod]=min(minn[nod],minn[it]+1);
}
if(dist[nod]==x)
{
++cnt; dist[nod]=-x-1;
aux.pb(nod);
return;
}
int maxx=-INF;
for(auto it : L[nod])
{
if(it==tata || it==Node) continue;
maxx=max(maxx,x-(minn[it]+2+x));
}
if(nod==1 && maxx < 1+dist[1])
{
++cnt; aux.pb(1);
}
}
inline bool Ok(int d)
{
x=d; cnt=0;
for(int i=1;i<=n;++i)
{
dist[i]=0; minn[i]=INF;
}
aux.clear();
Dfs(1,0);
return (cnt<=k);
}
int main()
{
int i,x,y;
ifstream cin("salvare.in");
ofstream cout("salvare.out");
cin>>n>>k;
for(i=1;i<n;++i)
{
cin>>x>>y;
L[x].pb(y); L[y].pb(x);
}
int st=0,dr=n,mij,sol;
while(st<=dr)
{
mij=((st+dr)>>1);
if(Ok(mij))
{
sol=mij;
ans.clear();
for(auto it : aux) ans.pb(it);
dr=mij-1;
}
else st=mij+1;
}
cout<<sol<<"\n";
sort(ans.begin(),ans.end());
for(auto it : ans) cout<<it<<" ";
cout<<"\n";
}