Cod sursa(job #3243112)

Utilizator Luca529Taschina Luca Luca529 Data 15 septembrie 2024 20:45:38
Problema Salvare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <vector>
#include <algorithm>

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

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);
    }

    if(k==n)
    {fout<<"0\n";
     for(int i=1;i<=n;i++)
     fout<<i<<" ";
    }
    else
    {st=1, dr=sol=n;
     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;
}