Pagini recente » Cod sursa (job #1797831) | Cod sursa (job #944765) | Cod sursa (job #554258) | Cod sursa (job #1813044) | Cod sursa (job #1566258)
#include <bits/stdc++.h>
#define Nmax 1005
#define INF 1000000000
#define pb push_back
using namespace std;
int dp[Nmax][Nmax],info[Nmax][Nmax],x,nr,n,k,NOD,Tatic[Nmax];
vector <int> L[Nmax],ans,aux,T[Nmax];
inline void Solve(int nod, int tata, int dist)
{
if(dist==x+1)
{
T[NOD].pb(nod); nr+=dp[nod][x]; return;
}
for(auto it : L[nod])
{
if(it==tata) continue;
Solve(it,nod,dist+1);
}
}
inline void Dfs(int nod, int tata)
{
int sum=0;
Tatic[nod]=tata;
for(auto it : L[nod])
{
if(it==tata) continue;
Dfs(it,nod); sum+=dp[it][x];
}
nr=0; NOD=nod; Solve(nod,tata,0);
dp[nod][0]=nr+1;
int i;
for(i=1;i<=x;++i)
{
int minn=INF,node;
for(auto it : L[nod])
{
if(it==tata) continue;
if(minn > -dp[it][x]+dp[it][i-1])
{
minn=-dp[it][x]+dp[it][i-1];
node=it;
}
}
dp[nod][i]=sum+minn;
info[nod][i]=node;
if(dp[nod][i-1] < dp[nod][i])
{
dp[nod][i]=dp[nod][i-1];
info[nod][i]=-1;
}
}
}
inline void Construct(int nod, int d)
{
//cout<<nod<<" "<<d<<"\n";
if(!d)
{
aux.pb(nod);
for(auto it : T[nod]) Construct(it,x);
return;
}
if(info[nod][d]==-1) Construct(nod,d-1);
else
{
for(auto it : L[nod])
{
if(it==Tatic[nod]) continue;
if(it==info[nod][d]) Construct(it,d-1);
else Construct(it,x);
}
}
}
inline bool Ok(int d)
{
int i,j;
for(i=1;i<=n;++i)
for(j=0;j<=n;++j) dp[i][j]=INF;
for(i=1;i<=n;++i) T[i].clear();
x=d; Dfs(1,0);
if(dp[1][x]>k) return 0;
aux.clear();
Construct(1,x);
return 1;
}
int main()
{
int i,x,y,st,dr,mij,sol;
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);
}
st=0; dr=n;
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";
//cout<<Ok(1)<<"\n";
return 0;
}