Cod sursa(job #2531302)

Utilizator florin_salamFlorin Salam florin_salam Data 26 ianuarie 2020 02:27:09
Problema Salvare Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1005;
int N, K;
int point[NMAX], dist[NMAX];
vector <int> graph[NMAX];

void dfs(int node, int father, const int len)
{
    if (graph[node].size() == 1 && node != 1)
    {
        dist[node] = len + 1;
        return;
    }
    int mx = 0, mn = (1 << 30);
    for (auto& i : graph[node])
        if (i != father)
        {
            dfs(i, node, len);
            mx = max(mx, dist[i] + 1);
            mn = min(mn, dist[i] + 1);
        }
    dist[node] = mx;
    if (mx > 2 * len)
    {
        dist[node] = 0;
        point[node] = true;
        return;
    }
    if (mn <= len && mn + mx - 1 <= 2 * len)
        dist[node] = mn;
}

int Solve(int len)
{
    for (int i = 1;i <= N;++i)
        point[i] = dist[i] = 0;
    dfs(1, 0, len);
    int cnt = 0;
    for (int i = 1;i <= N;++i)
        cnt += point[i];
    if (dist[1] > len)
    {
        point[1] = true;
        ++cnt;
    }
    return cnt;
}

int main()
{
    ifstream fin("salvare.in");
    ofstream fout("salvare.out");
    fin >> N >> K;
    for (int i = 1;i < N;++i)
    {
        int u, v;
        fin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int left = 1, right = N, mid, answer;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (Solve(mid) <= K)
        {
            answer = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    Solve(answer);
    fout << answer << "\n";
    for (int i = 1;i <= N;++i)
        if (point[i])
            fout << i << " ";
    fin.close();
    fout.close();
    return 0;
}