ZOJ 3201 Tree of Tree

Tree of Tree

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on ZJU. Original ID: 3201
64-bit integer IO format: %lld      Java class name: Main

 

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.

Input

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.

Output

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

Sample Input

3 1
10 20 30
0 1
0 2
3 2
10 20 30
0 1
0 2

Sample Output

30
40

 

Source

ZOJ Monthly, May 2009

Author

LIU, Yaoting

 

解题：树形dp，dp[i][j]表示以i为根选j个的最大权和

 

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 200;
vector<int>g[maxn];
int w[maxn],dp[maxn][maxn],n,m,ret;
void dfs(int u,int fa){
    memset(dp[u],0,sizeof dp[u]);
    dp[u][1] = w[u];
    for(int i = g[u].size()-1; i >= 0; --i){
        if(g[u][i] == fa) continue;
        dfs(g[u][i],u);
        for(int j = m; j; --j)
            for(int k = 0; k < j; ++k)
                dp[u][j] = max(dp[u][j],dp[u][j-k] + dp[g[u][i]][k]);
    }
    ret = max(dp[u][m],ret);
}
int main(){
    int u,v;
    while(~scanf("%d%d",&n,&m)){
        for(int i = 0; i < maxn; ++i) g[i].clear();
        for(int i = 0; i < n; ++i) scanf("%d",w+i);
        for(int i = 1; i < n; ++i){
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        ret = 0;
        dfs(0,-1);
        printf("%d
",ret);
    }
    return 0;
}