Cod sursa(job #3300392)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 15 iunie 2025 12:50:32
Problema Salvare Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define nmax 1005
using namespace std;
ifstream cin("salvare.in");
ofstream cout("salvare.out");
int n,k,x,y,d[nmax];
bool viz[nmax],in[nmax];
vector<int>v[nmax],sol;
void dfs(int nod,int dist){
    viz[nod]=1;
    d[nod]=0;
    for(auto i:v[nod])
        if(!viz[i]){
            dfs(i,dist);
            d[nod]=max(d[nod],d[i]);
        }
    if(d[nod]==dist){
        sol.push_back(nod);
        d[nod]=-dist;
    }else
        d[nod]++;
}
int verif(int dist){
    sol.clear();
    memset(viz,0,sizeof(viz));
    dfs(1,dist);
    return sol.size();
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int r=n,st=0,dr=n;
    while(st<=dr){
        int mid=(st+dr)/2;
        if(verif(mid)<=k)
            r=mid,dr=mid-1;
        else
            st=mid+1;
    }
    cout<<r<<'\n';
    verif(r);
    r=sol.size();
    for(auto i:sol)
        in[i]=1;
    for(int i=1;i<=n&&r<k;i++)
        if(!in[i]){
            r++;
            sol.push_back(i);
        }
    sort(sol.begin(),sol.end());
    for(auto i:sol)
        cout<<i<<" ";
    return 0;
}