zoj 3201

Tree of Tree Time Limit: 1 Second       Memory Limit: 32768 KB

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
      

Author:  LIU, Yaoting

Source: ZOJ Monthly, May 2009

題意:

給你有n的點的樹和要求的子樹的點數，下一行跟的是n個點的權值，然後跟着n-1條邊連着這些點，求該n個點的樹的子樹中權值和最大的是多少？(需要滿足子樹點為k個)

分析：

首先想子樹要被選中那麼它的根節點必定要選，然後該節點被選中，它下面有很多個子樹，一些要被選中，一些不用被選中，那麼就是一個背包問題了。

開一個dp[u][j]的二維數組u表示目前根節點，j表示這個樹下面有多少個點。

而dp[u][1]=a[u]是顯而易見的，那麼外層必定是j從k枚舉到1,再枚舉有多少個點在這個子樹上，多少個點不在這個子樹上即可！

即dp方程為dp[u][j]=max(dp[u][j],dp[u][kk]+dp[v][j-kk])(kk是在u上的點，j-kk是不在u上的點,v是u的子樹的根節點)

code:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[105];
struct s{
	int to,next,w;
}hehe[420];
int p[105],eid,dp[105][105],vis[105],k;
void init(){
	memset(p,-1,sizeof(p));
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
	eid=0;
}
void ljb(int from,int to,int w){
	hehe[eid].to=to;
	hehe[eid].w=w;
	hehe[eid].next=p[from];
	p[from]=eid++;
}
void dfs(int u){
	int v;
	vis[u]=1;
	dp[u][1]=a[u];
	for(int i=p[u];i!=-1;i=hehe[i].next){
		v=hehe[i].to;
		if(vis[v])
			continue;
		dfs(v);
		for(int j=k;j>=1;j--)
			for(int kk=1;kk<=j;kk++)
				dp[u][j]=max(dp[u][j],dp[u][kk]+dp[v][j-kk]);
	}
}
int main()
{
	int n,x,y;
	while(~scanf("%d%d",&n,&k)){
		init();
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<n;i++){
			scanf("%d%d",&x,&y);
			ljb(x,y,1);
			ljb(y,x,1);
		}
		dfs(0);
		int ans=0;
		for(int i=0;i<n;i++)
			if(dp[i][k]>ans)
				ans=dp[i][k];
		printf("%d\n",ans);
	}
}