poj 2486 Apple Tree 树形dp

浏览数：24 / 时间：2015年06月11日

// 好题！mark一下，不会写！参考这里的。。。
// http://hi.baidu.com/zyz913614263/item/86f442228b3db8042a0f1c65


// 上面的链接解释很详细了，我就不再废话了>_<。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> tree[105];
int a[105];
int dp[2][105][205];
int n,k;
int x,y;
void dfs(int now,int fa=-1)
{
    for(int i=0;i<=k;i++) dp[0][now][i]=dp[1][now][i]=a[now];
    for(int i=0;i<tree[now].size();i++)
    {
        int to=tree[now][i];
        if(to!=fa){
        dfs(to,now);
        for(int i=k;i>=0;i--)
        {
            for(int j=0;j<=i;j++)
            {
                dp[1][now][i+1]=max(dp[1][now][i+1],dp[0][now][i-j]+dp[1][to][j]);
                dp[1][now][i+2]=max(dp[1][now][i+2],dp[1][now][i-j]+dp[0][to][j]);
                dp[0][now][i+2]=max(dp[0][now][i+2],dp[0][now][i-j]+dp[0][to][j]);
            }
        }
        }
    }
}
int main()
{

    while(~scanf("%d%d",&n,&k))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),tree[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        dfs(1);

        printf("%d\n",dp[1][1][k]);
    }


    return 0;
}
/*
8 4
0 1 4 3 3 2 4 1
1 2
1 3
1 4
2 5
2 6
3 7
3 8
*/

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。