Cod sursa(job #3243108)

Utilizator Luca529Taschina Luca Luca529 Data 15 septembrie 2024 20:23:33
Problema Salvare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("salvare.in");
ofstream fout("salvare.out");
int dist[1005], v[1005], sum[1005], nr;
vector<int> x[1005];

int DFS(int a, int d)
{int max1=0, max2=0;
 sum[a]=dist[a]=0;

 vector<int>:: iterator I;
 for(I=x[a].begin();I<x[a].end();I++)
 if(dist[*I]==-1)
 {DFS(*I, d);

  if(dist[*I]+1>max1)max2=max1, max1=dist[*I]+1;
  else if(dist[*I]+1>max2)max2=dist[*I]+1;

  sum[a]+=sum[*I];
 }

 if(max1+max2>d)
 {sum[a]++;

  v[++nr]=a;
  dist[a]=0;
 }
 else dist[a]=max1+1;
}

int main()
{   int n, k, a, b, st, dr, mij, sol;
    fin>>n>>k;

    for(int i=1;i<n;i++)
    {fin>>a>>b;

     x[a].push_back(b);
     x[b].push_back(a);
    }

    st=1, dr=1000;
    while(st<=dr)
    {mij=(st+dr)/2;

     for(int i=1;i<=n;i++)
     dist[i]=-1;

     nr=0;
     DFS(1, mij);

     if(sum[1]<=k)sol=mij, dr=mij-1;
     else st=mij+1;
    }

    nr=0;
    for(int i=1;i<=n;i++)
    dist[i]=-1;

    DFS(1, sol);
    for(int i=1;i<=n && nr<k;i++)
    if(dist[i]!=0)v[++nr]=i;

    sort(v+1, v+1+nr);

    fout<<sol<<"\n";
    for(int i=1;i<=nr;i++)
    fout<<v[i]<<" ";

    return 0;
}