刚接触 树上背包。。有点抽象化 找好父亲和儿子的关系 及状态转移方程 

代码里有详细的注释  就不解释了

1 #include 
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define N 155 8 #define INF 0xfffffff 9 int n,m;10 int w[N][N],o[N],dp[N][N];11 void add(int u,int v)12 {13     w[u][o[u]++] = v;//不在乎内存的邻接表14 }15 void dfs(int root)16 {17     int i,j;18     for(i = 0; i <= m ; i++)19     dp[root][i] = INF;//类似背包的初始化 20     dp[root][1] = 0;//如果保留一个节点 就不需要切 那个加1 会在后面有21     for(i = 0; i < o[root] ; i++)22     {23         int son = w[root][i];24         dfs(son);//搜到叶子 树都这样25         for(j = m ; j>=0 ; j--)26         {27             int minz = INF,k;28             for(k = 0 ; k < j ; k++)29             minz = min(minz,dp[root][k]+dp[son][j-k]);//这个是对于本儿子来言 找一个能够让父亲保留J个节点的最好办法30             dp[root][j] = min(dp[root][j]+1,minz);//是保留之前j个节点的取法（就是不要本儿子 切掉） 还是要本儿子的方法31         }32     }33 }34 int main()35 {36     int i;37     while(scanf("%d",&n)!=EOF)38     {39         memset(o,0,sizeof(o));40         scanf("%d",&m);41         for(i = 1; i < n ;i++)42         {43             int u,v;44             scanf("%d%d",&u,&v);45             add(u,v);46         }47         dfs(1);48         int ans = dp[1][m];//树根的话就不用加切祖先那一刀了49         for(i = 2; i <= n ; i++)50         ans = min(ans,dp[i][m]+1);//剩下的都要+151         cout<
           
            <