树形背包。。。
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 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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int Adj[200],Size;
struct E
{
int to,next;
}Edge[40000];
void init()
{
Size=0;
memset(Adj,-1,sizeof(Adj));
}
void Add_Edge(int u,int v)
{
Edge[Size].to=v;
Edge[Size].next=Adj[u];
Adj[u]=Size++;
}
int n,K,dp[200][200];
void dfs(int f,int u)
{
for(int i=Adj[u];~i;i=Edge[i].next)
{
int v=Edge[i].to;
if(v==f) continue;
dfs(u,v);
for(int j=K;j>=1;j--)
{
for(int k=1;k<j;k++)
{
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&K)!=EOF)
{
init();
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++) scanf("%d",&dp[i][1]);
for(int i=0;i<n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
Add_Edge(u,v);
Add_Edge(v,u);
}
dfs(-1,0);
int ans=-INF;
for(int i=0;i<n;i++)
ans=max(ans,dp[i][K]);
printf("%d\n",ans);
}
return 0;
}