poj 1947 Rebuilding Roads ---树形DP

题意：给一棵树，求最少去掉几条边能得到一个节点数为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 <iostream>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <map>#define inf 0x3f3f3f3fusing 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<i;j++)            {                tmp=min(tmp,dp[r][j]+dp[s][i-j]);            }            dp[r][i]=tmp;        }        s=bro[s];    }}int main(){    int i,j,a,b,root,ans;    while(~scanf("%d%d",&n,&p))    {        memset(son,0,sizeof son);        memset(bro,0,sizeof bro);        memset(ro,0,sizeof ro);        for(i=1;i<n;i++)        {            scanf("%d%d",&a,&b);            bro[b]=son[a];            son[a]=b;            ro[b]=1;        }        for(i=1;i<=n;i++)        {            if(!ro[i])            {                root=i;                break;            }        }        for(i=1;i<=n;i++)        {            for(j=0;j<=p;j++)                dp[i][j]=inf;            dp[i][1]=0;        }        dfs(root);        ans=dp[root][p];        for(i=1;i<=n;i++)            ans=min(ans,dp[i][p]+1);        printf("%d\n",ans);    }    return 0;}