hdu 5834 Magic boy Bi Luo with his excited tree （树形dp）

题意：有一棵树包含n个点，n-1条边，每个点有个值value[i]，每条边有边权（即费用），问你以每个点作为开始点，向其他点走，走到一个点可以得到这个点的value，经过一条边会有费用，费用由value值支付，每个点的value值只能拿一次，没必要所有点都走到，问你可以得到的最大的value值，当value值不足以支付边权时也可以走。

分析：显而易见的树形dp，如果只从一个点出发，那么这个题就成了很裸的树形dp，关键这个题是要从每个点出发求相应的答案，我们只需要第二次dfs的时候找出每个点的答案即可。方法来源于上决——

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int val[maxn];
int p[maxn],num;
struct node
{
    int u,v,len,next;
    node(){}
    node(int u,int v,int len,int next): u(u),v(v),len(len),next(next) {}
}E[maxn*2];
void init()
{
    num=0;
    memset(p,-1,sizeof(p));
}
void add(int u,int len)
{
    E[num]=node(u,p[u]);
    p[u]=num++;
}
int max_back[maxn],max_notback[maxn],max_notback_id[maxn];
int submax_notback[maxn];
int ans[maxn];
void dfs1(int u,int fa)
{
    max_back[u]=max_notback[u]=val[u];
    submax_notback[u]=0;
    for(int i=p[u];~i;i=E[i].next)
    {
        int v=E[i].v;
        int len=E[i].len;
        if(v==fa) continue;
        dfs1(v,u);
    }
    for(int i=p[u];~i;i=E[i].next)
    {
        int v=E[i].v;
        int len=E[i].len;
        if(v==fa) continue;
        max_back[u]+=max(0,max_back[v]-2*len);
    }
    for(int i=p[u];~i;i=E[i].next)
    {
        int v=E[i].v;
        int len=E[i].len;
        if(v==fa) continue;
        int Len=max_back[u]-max(0,max_back[v]-2*len)+max(0,max_notback[v]-len);
        if(Len>max_notback[u])
        {
            submax_notback[u]=max_notback[u];
            max_notback[u]=Len;
            max_notback_id[u]=v;
        }
        else if(Len>submax_notback[u])
        {
            submax_notback[u]=Len;
        }
    }
}
void dfs2(int u,int fa,int fa_back,int fa_notback)
{
    ans[u]=max(fa_back+max_notback[u],fa_notback+max_back[u]);
    for(int i=p[u];~i;i=E[i].next)
    {
        int v=E[i].v;
        int len=E[i].len;
        if(v==fa) continue;
        int fb,fnb;
        if(v==max_notback_id[u])
        {
            fb=fa_back+max_back[u]-max(0,max_back[v]-2*len);
            fnb=max(fa_notback+max_back[u]-max(0,max_back[v]-2*len),fa_back+submax_notback[u]-max(0,max_back[v]-2*len));
        }
        else
        {
            fb=fa_back+max_back[u]-max(0,fa_back+max_notback[u]-max(0,max_back[v]-2*len));
        }
        dfs2(v,u,max(0,fb-2*len),fnb-len));
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++)
    {
        init();
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&val[i]);
        for(int i=1;i<n;i++)
        {
            int u,len;
            scanf("%d%d%d",&u,&v,&len);
            add(u,len);
            add(v,len);
        }
        dfs1(1,-1);
        dfs2(1,0);
        printf("Case #%d:n",ca);
        for(int i=1;i<=n;i++) printf("%dn",ans[i]);
    }
    return 0;
}

（编辑：青岛站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!