Cod sursa(job #1775612)

Utilizator LucianTLucian Trepteanu LucianT Data 10 octombrie 2016 16:33:00
Problema Salvare Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
#define maxN 1005
#define INF (1<<30)
using namespace std;
int dp[maxN],need[maxN];
vector<int>v[maxN],tempsol,sol;
int n,i,j,x,y,k,dist;
int st,dr,mij,ans;
void dfs(int nod,int tata)
{
    dp[nod]=INF,need[nod]=dist;
    for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
        if(*it!=tata)
        {
            dfs(*it,nod);
            dp[nod]=min(dp[nod],dp[*it]+1);
            need[nod]=min(need[nod],need[*it]-1);
        }
    if(dp[nod]<=need[nod])
        need[nod]=INF;
    if(!need[nod])
        dp[nod]=0,need[nod]=INF,
        tempsol.push_back(nod);
}
bool verif(int val)
{
    dist=val;
    tempsol.clear();
    dfs(1,0);
    if((int)tempsol.size()<=k)
        return true;
    return false;
}
int main()
{
    freopen("salvare.in","r",stdin);
    freopen("salvare.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<n;i++)
        scanf("%d %d",&x,&y),
        v[x].push_back(y),
        v[y].push_back(x);
    st=0,dr=n;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(verif(mij))
            ans=mij,sol=tempsol,dr=mij-1;
        else st=mij+1;
    }
    printf("%d\n",ans);
    for(size_t i=0;i<sol.size();i++)
        printf("%d ",sol[i]);
    return 0;
}