Cod sursa(job #2543833)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 11 februarie 2020 16:19:30
Problema Salvare Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e3 + 5;

ifstream cin("salvare.in");
ofstream cout("salvare.out");

vector <int> g[NMAX];
int dp[NMAX];
vector <int> salv;
vector <int> sol;

void dfs(int node, int father, int d)
{
    for(auto x: g[node]) {
        if(x != father) {
            dfs(x, node, d);
            dp[node] = max(dp[node], dp[x] + 1);
        }
    }
    if(dp[node] == d) {
        dp[node] = -d;
        salv.push_back(node);
        return;
    }
}

bool Check(int d, int n, int k)
{
    for(int i = 1; i <= n; ++i) {
        dp[i] = 0;
    }
    salv.clear();
    dfs(1, -1, d);
    if(salv.size() <= k) {
        return 1;
    } else {
        return 0;
    }
}

void CopySalv()
{
    sol.clear();
    for(int i = 0; i < salv.size(); ++i)
        sol.push_back(salv[i]);
}

int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int st = 0;
    int dr = n;
    int last = 0;
    while(st <= dr) {
        int med = (st + dr) / 2;
        if(Check(med, n, k)) {
            dr = med - 1;
            last = med;
            CopySalv();
        } else {
            st = med + 1;
        }
    }
    cout << last << "\n";
    sort(sol.begin(), sol.end());
    for(auto x: sol) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}