POJ1947: Rebuilding Roads(트리 DP)

Description
The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.
Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.
Input
* Line 1: Two integers, N and P
* Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J's parent in the tree of roads.
Output
A single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated.
Sample Input

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11

Sample Output

2

Hint
[A subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed.]
제목: n,p를 주십시오. 모두 n개의 노드가 있습니다. 최소한의 가장자리를 줄여야 합니다. 나머지 p개의 노드는
사고방식: 전형적인 트리 DP,
dp[s][i]: s결점을 기록하고 j개 노드의 자수를 얻어 아들 k1을 최소화해야 한다. 만약에 k자수를 제거하지 않으면 dp[s][i]=min(dp[s][j]+dp[k][i-j])0 <=j<=i
2) k자 트리를 제거하면 dp[s][i]=dp[s][i]+1 총 dp[s][i]=min(min(dp[s][j]+dp[k][i-j]), dp[s][i]+1)
 

#include 
#include 
#include 
using namespace std;

int n,p,root;
int dp[155][155];
int father[155],son[155],brother[155];

void dfs(int root)
{
    int i,j,k,tem;
    for(i = 0; i<=p; i++)
        dp[root][i] = 10000000;
    dp[root][1] = 0;
    k = son[root];
    while(k)
    {
        dfs(k);
        for(i = p; i>=1; i--)
        {
            tem = dp[root][i]+1;
            for(j = 1; j