Cod sursa(job #55651)

Utilizator dominoMircea Pasoi domino Data 27 aprilie 2007 23:06:05
Problema Salvare Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#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;
}