# 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 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;
for( i=0; i<n; i++ )
if( !sign[i] )
{
root = i;
break;
}
}
int main()
{
init();
creat(root);