Pagini recente » Cod sursa (job #2430272) | Cod sursa (job #1557167) | Cod sursa (job #2663014) | Cod sursa (job #311060) | Cod sursa (job #63316)
Cod sursa(job #63316)
#include <stdio.h>
#include <string.h>
#include <vector>
#define pb push_back
#define nmax 30005
#define kmax 105
#define inf (int)1e8
using namespace std;
int n,k,K,x1,y1,i,d[nmax],m[nmax],tata[nmax];
char v[nmax],bag[nmax];
vector <int> e[nmax];
inline int min(int a,int b) {
if(a > b) return b;
else return a;
}
void dfs(int x) {
v[x] = 1;
int ct = 0;
for(int i = 0; i < (int)e[x].size(); i++)
if(!v[e[x][i]]) {
ct++;
break;
}
if(!ct) {
d[x] = inf;
m[x] = k;
}
else {
d[x] = inf;
m[x] = 2 * k;
for(int i = 0; i < (int)e[x].size(); i++)
if(!v[e[x][i]]) {
tata[e[x][i]] = x;
dfs(e[x][i]);
d[x] = min(d[x],d[e[x][i]] + 1);
}
for(int i = 0; i < (int)e[x].size(); i++)
if(tata[e[x][i]] == x)
if(m[e[x][i]] - 1 < d[x] || m[e[x][i]] > k || d[x] >= inf) m[x] = min(m[x],m[e[x][i]] - 1);
}
if(m[x] == 0) {
bag[x] = 1;
d[x] = 0;
m[x] = 2 * k + 1;
}
}
int cauta(int f,int l) {
int r = l + 1;
while(f <= l) {
int mi = (f + l) / 2;
memset(v,0,sizeof(v));
memset(bag,0,sizeof(bag));
k = mi;
dfs(1);
if(m[1] <= k) bag[1] = 1;
int tot = 0;
for(int i = 1; i <= n; i++) tot += bag[i];
//printf("%d %d\n",mi,tot);
if(tot <= K) {
r = mi;
l = mi - 1;
}
else f = mi + 1;
}
return r;
}
int main() {
freopen("salvare.in","r",stdin);
freopen("salvare.out","w",stdout);
scanf("%d%d",&n,&K);
for(i = 1; i < n; i++) {
scanf("%d%d",&x1,&y1);
e[x1].pb(y1);
e[y1].pb(x1);
}
int x = cauta(0,n);
k = x;
memset(v,0,sizeof(v));
memset(bag,0,sizeof(bag));
dfs(1);
if(m[1] <= k) bag[1] = 1;
int tot = 0;
for(int i = 1; i <= n; i++) tot += bag[i];
printf("%d\n",k);
for(int i = 1; i <= n; i++)
if(!bag[i] && tot < K) {
bag[i] = 1;
tot++;
}
for(int i = 1; i <= n; i++)
if(bag[i]) printf("%d ",i); printf("\n");
return 0;
}