Cod sursa(job #169830)

Utilizator marius.pungaruMarius Pungaru marius.pungaru Data 2 aprilie 2008 00:57:02
Problema Salvare Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 2.8 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 max_depth = H[n], min_depth = H[n], aux, *p;
    
    
    for (p = T[n]; *p; p++)
        if (*p != f)
        {
           aux = resolve(*p, n, len);
           max_depth = max(max_depth, aux);
           min_depth = min(min_depth, aux);
        }
           
    if (max_depth - H[n] <= H[n] - min_depth && min_depth >= H[n])
       return min_depth;
    if (max_depth - min_depth < len)
       return max_depth;

    need_cabans++;
    U[n] = 1;
    max_depth -= (len << 1);
    
    return min(max_depth, min_depth);
}
/////
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;
}