Cod sursa(job #1571053)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 17 ianuarie 2016 01:22:06
Problema Salvare Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1010;

int N, K;
int nodes[NMAX];
vector<int> G[NMAX];

int DFS(int node, int from, int curr, int max) {
    int ret = 0;

    if (curr > max + 1 || curr == 1)
        nodes[node] = ret = 1;

    for (int next : G[node]) {
        if (next == from)
            continue;
        if (curr > max + 1)
            ret += DFS(next, node, 2, max);
        else
            ret += DFS(next, node, curr + 1, max);
    }

    return ret;
}

int MaxDepth(int node, int from, int curr) {
    if (G[node].size() == 1)
        return curr;

    int ret = -1;
    for (int next : G[node]) {
        if (node != from)
            continue;
        ret = max(ret, MaxDepth(next, node, curr + 1));
    }

    return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	#ifndef ONLINE_JUDGE
	assert(freopen("salvare.in", "r", stdin) != NULL);
    assert(freopen("salvare.out", "w", stdout) != NULL);
    assert(freopen("debug.err", "w", stderr) != NULL);
    #endif

    int i, j, x, y;

    cin >> N >> K;
    for (i = 0; i < N - 1; ++i) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    int root = 1, depth = MaxDepth(1, -1, 1);
    for (i = 2; i <= N; ++i) {
        int curr = MaxDepth(i, -1, 1);
        if (curr < depth) {
            depth = curr;
            root = i;
        }
    }

    int res = (1 << 10) - 1;
    for (int bit = (1 << 9); bit; bit >>= 1)
        if (DFS(root, -1, 1, res - bit) <= K)
            res -= bit;

    memset(nodes, 0, sizeof(nodes));

    cout << res << '\n';
    int num = K - DFS(root, -1, 1, res);
    for (i = 1; i <= N; ++i)
        if (nodes[i] == 1)
            cout << i << ' ';
        else if (num) {
            --num;
            cout << i << ' ';
        }
    cout << '\n';

	return 0;
}