Cod sursa(job #3148533)

Utilizator emazareMazare Emanuel emazare Data 2 septembrie 2023 14:07:40
Problema Salvare Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax = 1005, INF = 1000000000;
vector<int> L[Nmax];
int dp[Nmax];
bool b[Nmax];

int dfs(int node, int father, int d){
    int nr = 0;
    for(int son : L[node]){
        if(son!=father)
            nr+=dfs(son, node, d);
    }
    int nmin = INF,nmax = 0;
    if(L[node].size() == 1)
        dp[node] = d+1;
    else{
        for(int son : L[node]){
            if(son!=father){
                nmin = min(nmin, dp[son]);
                nmax = max(nmax, dp[son]);
            }
        }
        if((nmax == 2*d) || (node == 1 && nmax+nmin>=2*d)){
            dp[node] = 0;
            b[node] = 1;
            nr++;
        }
        else
            dp[node] = nmin+1;
    }
    return nr;
}

int main()
{
    int n,k,i,st,dr,mid,sol,nr;
    fin >> n >> k;
    for(i=1;i<n;i++){
        int x,y;
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    st = 1; dr = n; sol = n;
    while(st<=dr){
        mid = (st+dr)/2;
        for(i=1;i<=n;i++)
            b[i] = 0;
        nr = dfs(1,0,mid);
        if(nr<=k){
            sol = mid;
            dr--;
        }
        else
            st++;
    }
    fout << sol << '\n';
    for(i=1;i<=n;i++)
        b[i] = 0;
    nr = dfs(1,0,sol);
    for(i=1;i<=n;i++){
        if(b[i] == 1)
            fout << i << " ";
    }
    return 0;
}