| Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
Description
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 110 20 300 10 23 210 20 300 10 2
Sample Output
3040
Source
#include#include #include #include #include using namespace std;#define maxn 105int n,k,dp[maxn][maxn],val[maxn];vector edge[maxn];void dfs(int u,int y){ dp[u][1] = val[u]; for(int i = 0;i < edge[u].size();i ++) { int v = edge[u][i]; if(v == y) continue; dfs(v, u); for(int j = k;j > 0;j --) //相似01背包 for(int p = 0;p < j;p ++) { dp[u][j] = max(dp[u][j], dp[u][j-p] + dp[v][p]); } }}int main(){ int a, b,ans; while(scanf("%d%d", &n, &k) != EOF) { ans = -1; memset(dp, -1, sizeof(dp)); for(int i = 0;i < n;i ++) edge[i].clear(); for(int i = 0;i < n;i ++) scanf("%d", &val[i]); for(int i = 0;i < n-1;i ++) { scanf("%d%d",&a,&b); edge[a].push_back(b); edge[b].push_back(a); } dfs(0, -1); for(int i = 0;i < n;i ++) ans = max(ans, dp[i][k]); printf("%d\n", ans); } return 0;}