Poj Solution 1947

http://poj.org/problem?id=1947

#include <list>
#include <iostream>
using namespace std;
list< int > e[150];
int ans[150][151];
int n, p, answer;
int root;
int creat( int r )
{
    int i, j, n, m, c, temp[151];
    n = 1;
    ans[r][0] = 1;
    ans[r][1] = 0;
    list< int >::iterator iter;    
    for( iter = e[r].begin(); iter != e[r].end(); iter++ )
    {
        c = *iter;
        m = creat( c );
        for( i = 1; i<=n+m; i++ )
        {
            temp[i] = 99999;
            for( j = (i-n<0)?0:(i-n) ; j <= ( (i-1<m)?(i-1):m ) ; j++ )
            if( ans[c][j] + ans[r][i-j] < temp[i] )
            {
                temp[i] = ans[c][j] + ans[r][i-j];
            }
        }        
        for( i = 1; i<=n+m; i++ )
            ans[r][i] = temp[i];
        n += m;
    }
    if( ans[r][p] + (int) (r!=root) < answer ) answer = ans[r][p] + (int) (r!=root);
    return n ;
}
void init()
{
    int i, a, b, j;
    bool sign[150] = {0};
    scanf( "%d %d", &n, &p );
    for( i=0; i<n-1; i++ )
    {
        scanf( "%d %d", &a, &b );
        e[a-1].push_front( b-1 );
        sign[b-1] = true;
    }
    for( i=0; i<n; i++ )
    for( j=0; j<=n; j++ )
        ans[i][j] = 99999;
    answer = 99999;
    for( i=0; i<n; i++ )
    if( !sign[i] )
    {
        root = i;
        break;
    }
}
int main()
{
    init();
    creat(root);
    printf( "%dn", answer );
    return 0;
}