Cod sursa(job #1566777)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 12 ianuarie 2016 16:35:04
Problema Salvare Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
#define Nmax 1005
#define INF 1000000000
#define pb push_back

using namespace std;

int n,k,x,cnt,dist[Nmax];
vector <int> L[Nmax],aux,ans;

inline void Dfs(int nod, int tata)
{
    int minn=INF;
    for(auto it : L[nod])
    {
        if(it==tata) continue;
        Dfs(it,nod);
        dist[nod]=max(dist[nod],dist[it]+1);
        minn=min(minn,dist[it]+1);
    }
    if(dist[nod]==x)
    {
        ++cnt; dist[nod]=-x-1;
        aux.pb(nod);
    }
    if(dist[nod]>=0 && -(minn+1) >= dist[nod]+1)
    {
        dist[nod]=minn;
    }
}

inline bool Ok(int d)
{
    x=d; cnt=0;
    for(int i=1;i<=n;++i) dist[i]=0;
    aux.clear();
    Dfs(1,0);
    if(dist[1]>=0)
    {
        ++cnt; aux.pb(1);
    }
    return (cnt<=k);
}

int main()
{
    int i,x,y;
    ifstream cin("salvare.in");
    ofstream cout("salvare.out");
    cin>>n>>k;
    for(i=1;i<n;++i)
    {
        cin>>x>>y;
        L[x].pb(y); L[y].pb(x);
    }
    int st=0,dr=n,mij,sol;
    while(st<=dr)
    {
        mij=((st+dr)>>1);
        if(Ok(mij))
        {
            sol=mij;
            ans.clear();
            for(auto it : aux) ans.pb(it);
            dr=mij-1;
        }
        else st=mij+1;
    }
    cout<<sol<<"\n";
    sort(ans.begin(),ans.end());
    for(auto it : ans) cout<<it<<" ";
    cout<<"\n";
}