POJ2486:Apple Tree(樹形DP)

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’t 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.
The 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
題意：一顆樹，n個點（1-n），n-1條邊，每個點上有一個權值，求從1出發，走V步，最多能遍歷到的權值思路：樹形dp，比較經典的一個樹形dp。首先很容易就可以想到用dp[root][k]表示以root為根的子樹中最多走k時所能獲得的最多蘋果數，接下去我們很習慣地會想到將k步在root的所有子結點中分配，也就是進行一次背包，就可以得出此時狀態的最優解了，但是這裡還有一個問題，那就是在進行背包的時候，對於某個孩子son走完之後是否回到根結點會對後面是否還能分配有影響，為了解決這個問題，我們只需要在狀態中增加一維就可以了，用dp[root][k][0]表示在子樹root中最多走k步，最後還是回到root處的最大值，dp[root][k][1]表示在子樹root中最多走k步，最後不回到root處的最大值。由此就可以得出狀態轉移方程了：dp[root][j][0] = MAX (dp[root][j][0] , dp[root][j-k][0] + dp[son][k-2][0]);//從s出發，要回到s，需要多走兩步s-t,t-s,分配給t子樹k步，其他子樹j-k步，都返回
dp[root][j]][1] = MAX(  dp[root][j][1] , dp[root][j-k][0] + dp[son][k-1][1]) ;//先遍歷s的其他子樹，回到s，遍歷t子樹，在當前子樹t不返回，多走一步dp[root][j][1] = MAX (dp[root][j][1] , dp[root][j-k][1] + dp[son][k-2][0]);//不回到s（去s的其他子樹），在t子樹返回，同樣有多出兩步

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

struct node
{
    int u,v,val,next;
} tree[505];

int dp[205][405][2],head[205],val[205];
int len,n,k;

void add(int u,int v)
{
    tree[len].u = u;
    tree[len].v = v;
    tree[len].next = head[u];
    head[u] = len++;
}

void dfs(int root,int mark)
{
    int i,j,t,son;
    for(i = head[root]; i!=-1; i = tree[i].next)
    {
        son = tree[i].v;
        if(son == mark)
            continue;
        dfs(son,root);
        for(j = k; j>=1; j--)
        {
            for(t = 1; t<=j; t++)
            {
                dp[root][j][0]=max(dp[root][j][0],dp[root][j-t][1]+dp[son][t-1][0]);
                dp[root][j][0]=max(dp[root][j][0],dp[root][j-t][0]+dp[son][t-2][1]);
                dp[root][j][1]=max(dp[root][j][1],dp[root][j-t][1]+dp[son][t-2][1]);
            }
        }
    }
}

int main()
{
    int i,j,a,b;
    while(~scanf("%d%d",&n,&k))
    {
        memset(dp,0,sizeof(dp));
        memset(head,-1,sizeof(head));
        for(i = 1; i<=n; i++)
        {
            scanf("%d",&val[i]);
            for(j = 0; j<=k; j++)
                dp[i][j][0] = dp[i][j][1] = val[i];
        }
        len = 0;
        for(i = 1; i<n; i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        dfs(1,0);
        printf("%d\n",max(dp[1][k][0],dp[1][k][1]));
    }

    return 0;
}