Cod sursa(job #3243132)

Utilizator Luca529Taschina Luca Luca529 Data 15 septembrie 2024 21:44:22
Problema Salvare Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 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];

void DFS(int a, int d)
{int max1=-1, ok=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)max1=dist[*I]+1;

  if(dist[*I]+1>=d || (a==1 && dist[*I]>0 && sum[*I]!=0))ok=1;
  sum[a]+=sum[*I];
 }

 if(ok)
 {sum[a]++;

  v[++nr]=a;
  dist[a]=-(d+1);
 }
 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;
}