树树
时间限制：1秒内存限制：32768KB
你给一个树的每个节点的权重，你需要找到这棵树的指定大小的最大子树。
树定义
树是其中不包含任何周期的连通图。
输入
有在输入多个测试用例。
每种情况下的第一行是两个整数N（1<=N<=100），K（1<=K<=N），其中N是该树的节点的数量，K是子树的大小，其次通过与N的非负整数，其中第k个整数表示第k个节点的权重的行。接下来的N-1行描述了树，每行有两个整数这意味着在这两个节点之间的边缘。以上所有的指标都是零基础，这是保证树的描述是正确的。
产量
一行与对于每种情况，这是最大的子树的总权重的单个整数。
样例输入
31
102030
01
02
32
102030
01
02
样例输出
30
40
树型DP+背包问题！
f[i][j]表示以i为根结点有j个结点子树的最大权值。
以下代码仅供参考！
#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;#define MAX 105vector<int> adj[MAX];int f[MAX][MAX],tot[MAX],weight[MAX];int ans,K;int max(int a,int b){return a>b?a:b;}int DFS(int u,int father){tot[u]=1;int i,j,k,v;for(i=0;i<adj[u].size();i++){v=adj[u][i];if(v==father) // 如果又回到了父节点的情况continue;tot[u]+=DFS(v,u);}f[u][1]=weight[u];for(i=0;i<adj[u].size();i++){v=adj[u][i];if(v==father)continue;for(j=tot[u];j>=1;j--){for(k=0;k<j&&k<=tot[v];k++){f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);}}}if(tot[u]>=K)ans=max(ans,f[u][K]);return tot[u];}int main(){int N,i,u,v;while(~scanf("%d%d",&N,&K)){for(i=0;i<N;i++){scanf("%d",&weight[i]);adj[i].clear();}for(i=1;i<N;i++){scanf("%d%d",&u,&v);adj[u].push_back(v);adj[v].push_back(u);}memset(f,0,sizeof(f));ans=0;DFS(1,-1);printf("%d\n",ans);}return 0;}
