poj 1947 Rebuilding Roads ---树形DP - c++编程基础

题意：给一棵树，求最少去掉几条边能得到一个节点数为p的子树

dp[i][j]存以第i个结点为根（相当于没有父亲的），得到一个结点为j的子树所要去掉的边数

从下到上搜索，

考虑一个节点时，有两种选择，

要么剪掉跟子节点相连的边，则dp[i][j] = dp[i][j]+1;

要么不剪掉，则d[i][j] = max(dp[i][j], dp[i][k]+dp[son][j-k]);

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define inf 0x3f3f3f3f  
using namespace std;  
  
int bro[160],son[160],ro[160],n,p,dp[160][160];  
  
void dfs(int r)  
{  
    int s,i,j,tmp;  
    s=son[r];  
    while(s)  
    {  
        dfs(s);  
        for(i=p;i>=0;i--)  
        {  
            tmp=dp[r][i]+1;//+1  
            for(j=1;j