Pagini recente » Cod sursa (job #2789407) | Cod sursa (job #2118672) | Cod sursa (job #2755287) | Cod sursa (job #67227) | Cod sursa (job #3148526)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
const int Nmax = 1005;
vector<int> L[Nmax];
int dp[Nmax];
bool b[Nmax];
int dfs(int node, int father, int d){
int nr = 0;
for(int son : L[node]){
if(son!=father)
nr+=dfs(son, node, d);
}
int i,nmin,nmax;
if(L[node].size() == 1)
dp[node] = d+1;
else{
for(i=0;i<int(L[node].size());i++){
if(i == 0 && L[node][0]!=father)
nmin = nmax = dp[L[node][0]];
else if(i == 1 && L[node][0] == father)
nmin = nmax = dp[L[node][1]];
else if(L[node][i]!=father){
nmin = min(nmin, dp[i]);
nmax = max(nmax, dp[i]);
}
}
if((node>1 && nmax == 2*d && nmin>2*d-3) || (node == 1 && nmax>d && nmin>d-2) || (node == 1 && nmax == d && nmin == d)){
dp[node] = 0;
b[node] = 1;
nr++;
}
else
dp[node] = nmin+1;
}
return nr;
}
int main()
{
int n,k,i,st,dr,mid,sol,nr;
fin >> n >> k;
for(i=1;i<n;i++){
int x,y;
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
st = 1; dr = n; sol = n;
while(st<=dr){
mid = (st+dr)/2;
for(i=1;i<=n;i++)
b[i] = 0;
nr = dfs(1,0,mid);
if(nr<=k){
sol = mid;
dr--;
}
else
st++;
}
fout << sol << '\n';
for(i=1;i<=n;i++)
b[i] = 0;
nr = dfs(1,0,sol);
for(i=1;i<=n;i++){
if(b[i] == 1)
fout << i << " ";
}
return 0;
}