Cod sursa(job #169846)

Utilizator marius.pungaruMarius Pungaru marius.pungaru Data 2 aprilie 2008 01:37:26
Problema Salvare Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FIN "cabane.in"
#define FOUT "cabane.out"
#define MAX_N 100002

int *T[MAX_N], H[MAX_N], U[MAX_N], need_cabans, N, M;

inline int max(int a, int b)
{
       return a > b ? a : b;
}

inline int min(int a, int b)
{
       return a < b ? a : b;
}

int depths(int n, int f, int lev)
{
    int *p;
    
    H[n] = lev;
    for (p = T[n]; *p; p++)
        if (*p != f)
           depths(*p, n, lev + 1);
        
    return H[n];
}

int resolve(int n, int f, int len)
{
    int request = H[n] - len, *p;
    
    for (p = T[n]; *p; p++)
        if (*p != f)
           request = max(request, resolve(*p, n, len));
           
    if (request >= H[n])
       need_cabans++, U[n] = 1, request = H[n] - len - 1;
    
    return request;
}
/////
int deg[MAX_N], X[MAX_N], Y[MAX_N];
////
int main(void)
{
    int i, j, n, step, len;
/*
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    
    scanf("%d%d", &N, &M);
    for (i = 1; i <= N; i++)
    {
        scanf("%d", &n);
        T[i] = (int *) malloc(sizeof(int) * (n + 1));
        for (j = 0; j < n; j++)
            scanf("%d", &T[i][j]);
        T[i][j] = 0;
    }
*/    
///////
freopen("salvare.in", "r", stdin);
freopen("salvare.out", "w", stdout);

scanf("%d%d", &N, &M);
for (i = 1; i < N; i++)
{
    scanf("%d%d", &X[i], &Y[i]);
    deg[X[i]]++, deg[Y[i]]++;
}

for (i = 1; i <= N; i++)
    T[i] = (int *) malloc(sizeof(int) * (deg[i] + 1));
memset(deg, 0, sizeof(deg));
for (i = 1; i < N; i++)
{
    T[X[i]][deg[X[i]]++] = Y[i];
    T[Y[i]][deg[Y[i]]++] = X[i];
}
for (i = 1; i <= N; i++)
    T[i][deg[i]] = 0;
/////
    if (M >= N)
    {
       printf("0\n"); ///!!!!
       for (i = 1; i <= N; i++)
           printf("%d ", i);
    }

    depths(1, -1, 0);
    
    for (step = 1; step <= N; step <<= 1) ;
    for (len = N; step; step >>= 1)
        if (len - step > 0)
        {
           need_cabans = 0;
           if (resolve(1, -1, len - step) > 0)
              need_cabans++;
           if (need_cabans <= M)
              len -= step;
        }
    
    memset(U, 0, sizeof(U));
    need_cabans = 0;
    if (resolve(1, -1, len) > 0)
       need_cabans++, U[1] = 1;
/*
    printf("%d %d\n", len, need_cabans);
    for (i = 1; i <= N; i++)
        if (U[i])
           printf("%d ", i);
*/    
///
   printf("%d\n", len);
   for (i = 1; i <= N; i++)
       if (U[i])
          printf("%d ", i);
///
    return 0;
}