描述

 

You're given a tree with weights of each node, you need to find the maximum subtree of specified size of this tree.

Tree Definition 

A tree is a connected graph which contains no cycles.

 

输入

 

There are several test cases in the input.

The first line of each case are two integers N(1 <= N <= 100), K(1 <= K <= N), where N is the number of nodes of this tree, and K is the subtree's size, followed by a line with N nonnegative integers, where the k-th integer indicates the weight of k-th node. The following N - 1 lines describe the tree, each line are two integers which means there is an edge between these two nodes. All indices above are zero-base and it is guaranteed that the description of the tree is correct.

 

输出

 

One line with a single integer for each case, which is the total weights of the maximum subtree.

 

 

给一棵树（都是无向边，所以根的位置可以是任意的），求指定大小子树的最大重量和。

第一次自己做出树状DP题目，好开心~

dp[u][j] 表示，以 u 为根的子树，大小为 j 时，最大的重量和

则可以写出状态转移方程 dp[u][j] = max(dp[u][k] + dp[v][j-k])    v 为 u 的子树，为当前树大小为 k，子树大小为 j-k， 因为根结点是一定要地，所以 1<k<=j。

还是要注意，遍历树的大小的那个循环次序，是从大到小，类似于 0-1 背包的一维数组优化一样，要搞清楚数组中每一个格子存的状态到底是什么。

代码：

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAX = 105; struct Node{    int num, weight;    Node(){}    Node(int nn, int nw):num(nn), weight(nw){}}; vector
         
           tree[MAX];int vis[MAX];int dp[MAX][MAX];    //在 i 结点，结点数量为 j 时的最大重量 int w[MAX];int n, k;int ans;int dfs(int u);int main(){//    freopen("input.txt", "r", stdin);        while(cin >> n >> k){        for(int i=0; i
          
           > w[i];            tree[i].clear();        }        int u, v;        for(int i=1; i
           
            > u >> v; tree[u].push_back(v); tree[v].push_back(u); } ans = 0; for(int i=0; i
            
             =1; j--){ //一共 j 个 ,注意循环次序，从大到小，前面的状态要搞懂 for(int x=0; x