Pagini recente » Cod sursa (job #45358) | Cod sursa (job #57057) | Cod sursa (job #53686) | Cod sursa (job #46105) | Cod sursa (job #59184)
Cod sursa(job #59184)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX_N 1024
#define FIN "salvare.in"
#define FOUT "salvare.out"
#define INF 0x3f3f3f3f
#define mp make_pair
#define f first
#define s second
int N, K, G[MAX_N][MAX_N], deg[MAX_N], up[MAX_N], nv;
pair<int, int> V[MAX_N]; char U[MAX_N], sol[MAX_N];
void DFS(int n, int lev)
{
int *p;
V[nv++] = mp(lev, n);
for (p = G[n]; *p; p++)
if (*p != up[n]) { up[*p] = n; DFS(*p, lev-1); }
}
void DFS2(int n, int up, int d)
{
int *p;
U[n] = 1;
if (d == 0) return;
for (p = G[n]; *p; p++)
if (*p != up) DFS2(*p, n, d-1);
}
int works(int D)
{
int i, j, d, ret = 0;
memset(U, 0, sizeof(U));
memset(sol, 0, sizeof(sol));
for (i = 0; i < nv; i++)
{
if (U[j = V[i].s]) continue;
for (d = D; up[j] && d; j = up[j], d--);
sol[j] = 1; ret++;
DFS2(j, 0, D);
}
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, 0);
sort(V, V+nv);
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 (!sol[j]){ sol[j] = 1; K--; }
printf("%d\n", i);
for (j = 1; j <= N; j++)
if (sol[j]) printf("%d ", j);
printf("\n");
return 0;
}