/* Apple Tree * Time Limit: 1000MS Memory Limit: 65536K * Total Submissions: 3608 Accepted: 1074 Description * Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to * an apple tree. There are N nodes in the tree. Each node has an amount of * apples. Wshxzt starts her happy trip at one node. She can eat up all the * apples in the nodes she reaches. HX is a kind guy. He knows that eating too * many can make the lovely girl become fat. So he doesn鈥檛 allow Wshxzt to go * more than K steps in the tree. It costs one step when she goes from one node * to another adjacent node. Wshxzt likes apple very much. So she wants to eat * as many as she can. Can you tell how many apples she can eat in at most K steps. Input * There are several test cases in the input * Each test case contains three parts. * The first part is two numbers N K, whose meanings we have talked about * just now. We denote the nodes by 1 2 ... N. Since it is a tree, each * node can reach any other in only one route. (1<=N<=100, 0<=K<=200) The * second part contains N integers (All integers are nonnegative and not * bigger than 1000). The ith number is the amount of apples in Node i. * he third part contains N-1 line. There are two numbers A,B in each line, * meaning that Node A and Node B are adjacent. * Input will be ended by the end of file. Note: Wshxzt starts at Node 1. Output * For each test case, output the maximal numbers of apples Wshxzt can eat at a line. Sample Input 2 1 0 11 1 2 3 2 0 1 2 1 2 1 3 Sample Output 11 2 Source * POJ Contest,Author:magicpig@ZSU
分析：
典型树形DP，转移方程
get[0][g][i+j+2（因为返回所以走来回+2）]=max(get[0][g][i+j+2],get[0][g][i]+get[0][now][j]);//1 回到根节点 get[1][g][i+j+1（不返回走一次）]=max(get[1][g][i+j+1],get[0][g][i]+get[1][now][j]);//2_1 在now这个子树不返回 get[1][g][i+j+2（其他节点不返回，此子节点返回，走来回）]=max(get[1][g][i+j+2],get[1][g][i]+get[0][now][j]);//2_2 在now子树返回，在其他子树不返回 没啥好说的 */
#include <iostream> using namespace std; int tree[101][101],get[2][101][205],n,k; bool p[101]; void dp(int g) { get[1][g][0]=get[0][g][0]; for(int i=1;i<=k;++i)get[0][g][i]=get[1][g][i]=get[0][g][0];//Very important 当时忘记赋初值了。。。 p[g]=1; for(int t=1;t<=tree[g][0];++t) if(!p[tree[g][t]]) { int now=tree[g][t]; dp(now); for(int i=k-1;i>=0;--i) for(int j=k-i;j>=0;--j) { get[0][g][i+j+2]=max(get[0][g][i+j+2],get[0][g][i]+get[0][now][j]);//1 回到根节点 get[1][g][i+j+1]=max(get[1][g][i+j+1],get[0][g][i]+get[1][now][j]);//2_1 在now这个子树不返回 get[1][g][i+j+2]=max(get[1][g][i+j+2],get[1][g][i]+get[0][now][j]);//2_2 在now子树返回，在其他子树不返回 } } } int main(int argc, char** argv) { // freopen("a.in","r",stdin); //freopen("a.out","w",stdout); while(cin>>n>>k) { memset(tree,0,sizeof(tree)); memset(get,0,sizeof(get)); memset(p,0,sizeof(p)); for(int i=1;i<=n;++i)cin>>get[0][i][0]; for(int i=1;i<n;++i) { int x,y; cin>>x>>y; ++tree[x][0]; tree[x][tree[x][0]]=y; ++tree[y][0]; tree[y][tree[y][0]]=x; } dp(1); cout<<get[1][1][k]<<endl; } return 0; }
