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
题意：求大小为k权值最大的子树。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN=105; vector<int> tree[MAXN]; int n,k; int w[MAXN]; int res; int dp[MAXN][MAXN]; void dfs(int u,int fa) { dp[u][1]=w[u]; for(int i=0;i<tree[u].size();i++) { int v=tree[u][i]; if(v==fa) continue; dfs(v,u); for(int j=k;j>=0;j--) for(int l=1;l<=j;l++) dp[u][k]=max(dp[u][k],dp[u][l]+dp[v][j-l]); } } int main() { while(scanf("%d%d",&n,&k)!=EOF) { memset(dp,0,sizeof(dp)); res=0; for(int i=0;i<n;i++) { tree[i].clear(); scanf("%d",&w[i]); } for(int i=0;i<n-1;i++) { int u,v; scanf("%d%d",&u,&v); tree[u].push_back(v); tree[v].push_back(u); } dfs(0,-1); for(int i=0;i<n;i++) res=max(dp[i][k],res); printf("%d ",res); } return 0; }