Cod sursa(job #2390034)

Utilizator robx12lnLinca Robert robx12ln Data 27 martie 2019 18:30:19
Problema Salvare Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("salvare.in");
ofstream fout("salvare.out");

int N, K, V[1005], cnt, f[1005];
vector<int> Sol, edge[1005];

void dfs( int D, int nod ){
    f[nod] = 1; bool ok = false;
    for( int v : edge[nod] ){
        if( f[v] == 0 ){
            ok = true;
            dfs( D, v );
        }
    }

    if( ok == false ){
        V[nod] = D;
    }else{
        for( int v : edge[nod] )
            if( f[v] == 0 )
                V[nod] = min( V[nod], V[v] - 1 );
        if( V[nod] == 0 )
            ++cnt, V[nod] = 2 * D;
    }
    f[nod] = 0;
}

void solve( int D, int nod ){
    f[nod] = 1; bool ok = false;
    for( int v : edge[nod] ){
        if( f[v] == 0 ){
            ok = true;
            solve( D, v );
        }
    }

    if( ok == false ){
        V[nod] = D;
    }else{
        for( int v : edge[nod] )
            if( f[v] == 0 )
                V[nod] = min( V[nod], V[v] - 1 );
        if( V[nod] == 0 )
            Sol.push_back( nod ), V[nod] = 2 * D;
    }
    f[nod] = 0;
}

int main(){

    fin >> N >> K;
    for( int i = 1; i < N; ++i ){
        int x, y; fin >> x >> y;
        edge[x].push_back( y );
        edge[y].push_back( x );
    }

    if( N <= K ){
        fout << "0\n";
        for( int i = 1; i <= N; i++ )
            fout << i << " ";
        return 0;
    }

    int st = 1, dr = N, mid;
    while( st <= dr ){
        mid = ( st + dr ) >> 1;
        cnt = 0;
        memset( V, 0x3f3f3f3f, sizeof(V) );
        dfs( mid, 1 );
        if( cnt <= K )
            dr = mid - 1;
        else
            st = mid + 1;
    }

    solve( st, 1 );
    sort( Sol.begin(), Sol.end() );
    fout << st << "\n";
    for( int i = 0; i < Sol.size(); i++ )
        fout << Sol[i] << " ";
    return 0;
}