Pagini recente » Cod sursa (job #3033069) | Cod sursa (job #348597) | Cod sursa (job #1443473) | Cod sursa (job #659363) | Cod sursa (job #55651)
Cod sursa(job #55651)
#include <stdio.h>
#include <string.h>
#define MAX_N 1024
#define FIN "salvare.in"
#define FOUT "salvare.out"
#define min(a, b) ((a) < (b) ? (a) : (b))
int N, K, G[MAX_N][MAX_N], up[MAX_N], deg[MAX_N], Q[MAX_N], D[MAX_N];
char U[MAX_N];
void DFS(int n)
{
int *p;
U[n] = 1;
for (p = G[n]; *p; p++)
if (!U[*p]) { up[*p] = n; DFS(*p); }
}
int works(int x)
{
int i, *p, ql = 0, qr = -1, ret = 0;
memset(D, 0x3f, sizeof(D));
memset(U, 0, sizeof(U));
for (i = 1; i <= N; i++)
{
for (deg[i] = 0, p = G[i]; *p; p++) deg[i]++;
if (deg[i] == 1) D[Q[++qr] = i] = x;
}
for (; ql <= qr; ql++)
{
deg[i = Q[ql]]--;
if (!up[i]) continue;
if (!D[i]) { D[i] = x+1; U[i] = 1; ret++; }
D[up[i]] = min(D[up[i]], D[i]-1);
if (--deg[up[i]] == 1) Q[++qr] = up[i];
}
if (!ret) { ret++; U[1] = 1; }
return ret;
}
int main(void)
{
int i, j, inc;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d %d", &N, &K);
for (inc = 1; inc < N; inc++)
{
scanf("%d %d", &i, &j);
G[i][deg[i]++] = j;
G[j][deg[j]++] = i;
}
DFS(1);
for (inc = 1; inc < N; inc <<= 1);
for (i = N; inc; inc >>= 1)
if (i-inc >= 0 && works(i-inc) <= K) i -= inc;
K -= works(i);
for (j = 1; j <= N && K; j++)
if (!U[j]){ U[j] = 1; K--; }
printf("%d\n", i);
for (j = 1; j <= N; j++)
if (U[j]) printf("%d ", j);
printf("\n");
return 0;
}