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 30
0 1
0 2
3 2
10 20 30
0 1
0 2
Sample Output
3040
/**
input:
12 4
40 20 50 30 80 10 70 10 10 20 30 30
0 1
1 2
2 5
4 5
3 5
2 6
2 9
6 7
6 8
9 10
9 11
output:
210
**/
// author: jfo()
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
#define M 100
int N, K;
int weight[M];
vector<int> neighbor[M];
int w[M][M+1];
void add(int index, int from)
{
w[index][1] = weight[index];
for(int i=0; i<neighbor[index].size(); i++) {
int c_index = neighbor[index][i];
if(c_index == from)
continue;
add(c_index, index);
int tmp[M+1];
for(int a=1; a<=K; a++) {
int max_w = 0;
for(int b=1; b<=a; b++) {
int thiz_w = w[index][b] + w[c_index][a-b];
if(thiz_w > max_w)
max_w = thiz_w;
}
tmp[a] = max_w;
}
// update this later
for(int j=1; j<=K; j++)
w[index][j] = tmp[j];
}
}
int max_subtree()
{
add(0, -1);
int m = 0;
for(int i=0; i<N; i++) {
if(w[i][K] > m)
m = w[i][K];
}
return m;
}
int main()
{
int i, j;
int p1, p2;
while(cin >> N >> K) {
for(i=0; i<N; i++)
cin >> weight[i];
for(i=0; i<N; i++)
neighbor[i].clear();
for(i=0; i<N-1; i++) {
cin >> p1 >> p2;
neighbor[p1].push_back(p2);
neighbor[p2].push_back(p1);
}
for(i=0; i<N; i++)
for(j=0; j<K+1; j++)
w[i][j] = 0;
cout << max_subtree() << endl;
}
return 0;
}