HDU - 5834 Magic boy Bi Luo with his excited tree 树形dp 好

题目链接

题意:

给你一棵树,每个结点有个宝藏价值w,每次只能拿一次宝藏,每次经过路径需要花费val值,路径可以来回经过,同时可以多次花费val值,求从i点出发,能拿到的最大权值ans【i】.

思路:

很明显是一个tree dp,但是难点在于怎么去维护,或者说想不全,只能想出一部分。当时也困在如何往父亲走,没法往上dfs.

首先以每个i结点为根节点往下走这个很好维护,我们设dp[i][0]表示从i结点往子树结点走,最后走回i点的最大收益,dp[i][1]表示从i结点往下走,把所有不亏的走完最后不返回i的最大值,dp[i][2]为次大值,id[x]表示dp[i][1]最大值最后是从哪一条边离开的.（为什么要记录从哪条边离开的下面会提到）

我们先来说说怎么求上面这些东西,首先dfs处理好 dp[i][0] .
然后处理dp[i][1],dp[i][2]。 假设当前是父节点x,枚举子节点u（枚举把不亏的都走完从结点u一直往下走了）,我们知道dp[x][0]表示从x往下走走回来的,那么有 now = dp[x][0] - max(0,dp[u][0]-2w)+max(0,dp[u][1]-w)
即如果原来为+ 那肯定走过u了 又回去x了 要减掉,如果dp[u][1]-w不为负就要走获得更大收益.

往下走的处理好了,我们再来处理往上走的,这里就需要用到id[x]，我们第二次dfs定义两个参数,up1,up2,表示x的父节点fa,走出去不回来的最大值,up2表示走出去再回来的最大值.
对于一个点x 他的最大收益只取决于两个 max(dp[x][0]+up1,dp[x][1]+up2)
即 max(往下走回来+父节点走出去不回来，往下走不回来+父节点走出去回来)

怎么维护？ 对于x和下一步要走的u点,如果id[x] == u,那么就up1就只能用次大值了,否则才可以用最大值. 对于up2就只能看他自己这个分支走没走到,走到就减去否则不减.这个过程是从下往上维护的,所以对于每个x,他的父节点的已经是最优的了.特殊处理一下根节点即可
具体的见代码吧,注释尽量详细一点

#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair 
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;
ll val[maxn];
ll ans[maxn];
vector<pair<ll,ll> > vt[maxn];
ll dp[maxn][4],id[maxn];
/*dp[i][0]从i往下返回i的最大值. dp[i][1]从i往下最后不返回i的最大值 dp[i][2]从i往下最后不返回i的次大值 id[i]表示从i往下最后不返回i的最大值，最后是从哪条边离开的 */ 
void init()
{
    for(int i = 0;i <= n;++i)
    {
        vt[i].clear();//忘记清空,给我一顿RE啊 = = 
        val[i] = 0;
        ans[i] = 0;
        dp[i][0] = dp[i][1] = dp[i][2] = id[i] = 0;
    }
    return ;
}
void dfs1(int x,int fa)
{
    dp[x][0] = val[x];
    for(int i  = 0;i < vt[x].size();++i)
    {
         ll u = vt[x][i].first;
         ll w = vt[x][i].second;
         if(u == fa) continue;
         dfs1(u,x);
         dp[x][0] += max((ll)0,dp[u][0] - 2*w);
         //先处理dp[x][0] 走出去回来的最大值 
    }
    //处理dp[][1]，dp[][2],id[x] 
    id[x] = -1;
    dp[x][1] = dp[x][2] = val[x];
    for(int i = 0; i < vt[x].size();++i)
    {
        ll u = vt[x][i].first;
        ll w = vt[x][i].second;
        if(u == fa) continue;
        ll now = dp[x][0] - max((ll)0,dp[u][0] - 2*w) + max((ll)0,dp[u][1] - w);
        //dp[x][0]是回来的,要减去dp[u][0]的因为从这支离开都走一次 
        if(now > dp[x][1])
        {
            dp[x][2] = dp[x][1];
            dp[x][1] = now;
            id[x] = i;
        }
        else if(dp[x][2] < now)
        dp[x][2] = now;
    }
}
void dfs2(int x,int fa,ll up1,ll up2)
{
// up1 x 的父节点走出去不回来的最大值
// up2 x 的父节点走出去回来的最大值 
    ans[x] = max(up1+dp[x][0],up2+dp[x][1]);
    for(int i = 0;i < vt[x].size();++i)
    {
        ll u = vt[x][i].first;
        ll w = vt[x][i].second;
        if(u == fa) continue;
        ll down1,down2;
        //down1 下一步的走出去不回来的最优解
        //down2 下一步的走出去回来的最优解 
        if(id[x] == i)//是最优只能走次优了 
        down1 = dp[x][2] - max((ll)0,dp[u][0]-2*w);
        else
        down1 = dp[x][1] - max((ll)0,dp[u][0]-2*w);

        down2 = max((ll)0,dp[x][0]-max((ll)0,dp[u][0]-2*w));
        //down1 要取两个的最优,因为这两种情况都是走出去不回来.
        //一个是把x子树都走光,从x的父亲离开,一个是把x父亲能走的走光从x下离开. 
        down1 = max((ll)0,max(up1+down2-w,up2+down1-w));
        down2 = max((ll)0,up2+down2-2*w);
        //down2的最优解等于x的fa的走出去回来的最优,加上x走出去回来的（但是要去掉u) 
        dfs2(u,x,down1,down2);
    }
    return ; 
}
int main(){

    int _;
    cin>>_;
    int ca = 1; 
    while(_--)
    {
        init();
        scanf("%d",&n);
        for(int i = 1;i <= n;++i)
        scanf("%lld",&val[i]);
        for(int i = 1;i < n;++i)
        {
            ll u,v,w;
            scanf("%lld %lld %lld",&u,&v,&w);
            vt[u].pb(mk(v,w));
            vt[v].pb(mk(u,w));
        }
        dfs1(1,0);
        dfs2(1,0,0);
        printf("Case #%d:n",ca++);
        for(int i = 1;i <= n;++i)
        printf("%lldn",ans[i]);
    }
    return 0;
}