Cod sursa(job #2542561)

Utilizator 12222Fendt 1000 Vario 12222 Data 10 februarie 2020 10:19:11
Problema Salvare Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 1001;

int n, k, lgsol;
int dist[Nmax], sol[Nmax];
vector <int> L[Nmax];

void Dfs(int tata, int nod, int &salvare, int lg)
{
    if(L[nod].size() == 1)
    {
        dist[nod] = 0;
        return ;
    }

    for(auto i : L[nod])
        if(i != tata)Dfs(nod, i, salvare, lg);

    dist[nod] = 0;
    for(auto i : L[nod])
        if(i != tata)dist[nod] = max(dist[nod], dist[i]);

    dist[nod]++;

    if(dist[nod] == lg)
    {
        dist[nod] = -lg;
        salvare--;
    }
}

int main()
{
    fin >> n >> k;

    int x, y;
    for(int i = 1; i < n; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }


    int salvare;
    int l, r, m, p;

    l = 1; r = Nmax - 1;
    while(l <= r)
    {
        m = (l + r) / 2;
        Dfs(0, 1, salvare = k, m);
        if(salvare >= 0)
        {
            r = m - 1;
            p = m;
            lgsol = 0;
            for(int i = 1; i <= n; i++)
                if(dist[i] == -m)sol[++lgsol] = i;

        }
        else l = m + 1;
    }


    fout << p << "\n";

    for(int i = 1; i <= lgsol; i++)
        fout << sol[i] << " ";

    fin.close();
    fout.close();
    return 0;
}