POJ - 1947Rebuilding Roads （树形DP）

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.] 

_______________________________________________________________________________________________________________________

dp[root][j]中保存的是，root为根节点的子树，得到 j 个节点的子树需要最少减掉的边数，

——————————————————————————————————————————————————

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int MAX = 1e5+10;
const int INF = 0x3fffffff;
const int N = 155;

int fa[N];
int dp[N][N];
int n,p;
int val[N];//记录一下有多少个子结点（包括自己）
vector<int>ve[N];

void DFS(int root){
    val[root] = 1;
    if(ve[root].size()==0){
        dp[root][1] = 0;//此时为叶结点，所以叶节点为根并且只留一个结点所需要删去0个边。
        return ;
    }
    for(int i=0;i<ve[root].size();i++){
        int child = ve[root][i];//子结点
        DFS(child);
        val[root] += val[child];//更新父节点的值
        for(int j=val[root];j>0;j--){
            for(int s=1;s<j;s++){
                dp[root][j] = min(dp[root][j-s]+dp[child][s]-1,dp[root][j]);
            }
        }
    }
}



int main(){
    while(scanf("%d%d",&n,&p)!=EOF){
        for(int i=0;i<=n;i++){
            ve[i].clear();
        }
        int x,y;
        memset(fa,0,sizeof(fa));
        memset(val,0,sizeof(val));
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                dp[i][j] = INF;
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&x,&y);
            ve[x].push_back(y);
        }
        for(int i=1;i<=n;i++)
            dp[i][1] = ve[i].size();
        DFS(1);
        int ans = dp[1][p];
        for(int i=1;i<=n;i++){
            ans = min(ans,dp[i][p]+1);
        }
        cout<<ans<<endl;
    }
    return 0;
}