Cod sursa(job #1607281)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 20 februarie 2016 23:02:18
Problema Salvare Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

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

const int N = 1010;

int n, k;
int dp[N];
bool vis[N];
vector < int > adj[N];

int cnt, dmax;
void dfs(int x, int p) {
    for(auto i : adj[x]) if(i != p) {
        dfs(i, x);
        dp[x] = max(dp[x], dp[i] + 1);
    }
    if(dp[x] == dmax) {
        dp[x] = 0;
        vis[x] = 1;
        cnt++;
    }
}

void get_min_dist() {
    int lo, hi, med;

    lo = 1;
    hi = n;
    while(lo <= hi) {
        med = (lo + hi) >> 1;
        cnt = 0; dmax = med;
        memset(dp, 0, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        dfs(1, 0);
        if(cnt <= k) {
            hi = med - 1;
        }
        else {
            lo = med + 1;
        }
    }

    memset(dp, 0, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    dmax = hi + 1;
    dfs(1, 0);
}

int main() {
    int i, u, v;

    in >> n >> k;
    for(i = 1; i < n; i++) {
        in >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    get_min_dist();
    out << dmax << '\n';
    k = k - cnt;
    for(i = 1; i <= n; i++) {
        if(vis[i]) {
            out << i << ' ';
        }
        else if(k > 0) {
            k--;
            out << i << ' ';
        }
    }

    return 0;
}