zju3201 Tree of Tree

发布时间:2014-10-22 19:12:10

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 树形 dp[i][j]表示 i节点的子树中有j个节点的最大value(j>=1时一定要包括自己) #include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,K,tot,ans; int pre[222],now[111],son[222]; int val[111],num[111]; int dp[111][111]; void add(int x,int y) { tot++; pre[tot]=now[x]; now[x]=tot; son[tot]=y; } void dfs(int u,int fa) { dp[u][1]=val[u]; int p=now[u]; while (p>0) { int v=son[p]; if (v!=fa) { dfs(v,u); for (int j=K; j>1; j--) for (int k=0; k<j; k++) dp[u][j]=max( dp[u][j], dp[v][k]+ dp[u][j-k] ); } p=pre[p]; } } int main() { while (scanf("%d%d",&n,&K)!=EOF) { memset(now,0,sizeof(now)); memset(dp,0 ,sizeof(dp)); tot=0; for (int i=0; i<n; i++) scanf("%d",&val[i]); for (int i=1; i<n; i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } ans=0; dfs( 0, -1 ); for (int i=0; i<n; i++) if ( dp[i][K]>ans ) ans=dp[i][K]; printf("%d\n",ans); } return 0; }