Cod sursa(job #3148526)

Utilizator emazareMazare Emanuel emazare Data 2 septembrie 2023 12:50:04
Problema Salvare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax = 1005;
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 i,nmin,nmax;
    if(L[node].size() == 1)
        dp[node] = d+1;
    else{
        for(i=0;i<int(L[node].size());i++){
            if(i == 0 && L[node][0]!=father)
                nmin = nmax = dp[L[node][0]];
            else if(i == 1 && L[node][0] == father)
                nmin = nmax = dp[L[node][1]];
            else if(L[node][i]!=father){
                nmin = min(nmin, dp[i]);
                nmax = max(nmax, dp[i]);
            }
        }
        if((node>1 && nmax == 2*d && nmin>2*d-3) || (node == 1 && nmax>d && nmin>d-2) || (node == 1 && nmax == d && nmin == 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;
}