Cod sursa(job #1566258)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 11 ianuarie 2016 22:21:01
Problema Salvare Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>
#define Nmax 1005
#define INF 1000000000
#define pb push_back

using namespace std;

int dp[Nmax][Nmax],info[Nmax][Nmax],x,nr,n,k,NOD,Tatic[Nmax];
vector <int> L[Nmax],ans,aux,T[Nmax];

inline void Solve(int nod, int tata, int dist)
{
    if(dist==x+1)
    {
        T[NOD].pb(nod); nr+=dp[nod][x]; return;
    }
    for(auto it : L[nod])
    {
        if(it==tata) continue;
        Solve(it,nod,dist+1);
    }
}

inline void Dfs(int nod, int tata)
{
    int sum=0;
    Tatic[nod]=tata;
    for(auto it : L[nod])
    {
        if(it==tata) continue;
        Dfs(it,nod); sum+=dp[it][x];
    }
    nr=0; NOD=nod; Solve(nod,tata,0);
    dp[nod][0]=nr+1;
    int i;
    for(i=1;i<=x;++i)
    {
        int minn=INF,node;
        for(auto it : L[nod])
        {
            if(it==tata) continue;
            if(minn > -dp[it][x]+dp[it][i-1])
            {
                minn=-dp[it][x]+dp[it][i-1];
                node=it;
            }
        }
        dp[nod][i]=sum+minn;
        info[nod][i]=node;
        if(dp[nod][i-1] < dp[nod][i])
        {
            dp[nod][i]=dp[nod][i-1];
            info[nod][i]=-1;
        }
    }
}

inline void Construct(int nod, int d)
{
    //cout<<nod<<" "<<d<<"\n";
    if(!d)
    {
        aux.pb(nod);
        for(auto it : T[nod]) Construct(it,x);
        return;
    }
    if(info[nod][d]==-1) Construct(nod,d-1);
    else
    {
        for(auto it : L[nod])
        {
            if(it==Tatic[nod]) continue;
            if(it==info[nod][d]) Construct(it,d-1);
            else Construct(it,x);
        }
    }
}

inline bool Ok(int d)
{
    int i,j;
    for(i=1;i<=n;++i)
        for(j=0;j<=n;++j) dp[i][j]=INF;
    for(i=1;i<=n;++i) T[i].clear();
    x=d; Dfs(1,0);
    if(dp[1][x]>k) return 0;
    aux.clear();
    Construct(1,x);
    return 1;
}

int main()
{
    int i,x,y,st,dr,mij,sol;
    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);
    }
    st=0; dr=n;
    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";
    //cout<<Ok(1)<<"\n";
    return 0;
}