hdu 5834 Magic boy Bi Luo with his excited tree

首先，如果要求的是以1作为开始位置的话，很容易想到一个dp[u][2]，其中dp[u][0]表示以u节点为开始位子的子树最后回到u节点获得最大值，dp[u][1]表示不回来。转移就显而易见了。

然后，考虑如果u节点结果已经计算出，怎么计算他的儿子节点v的答案。

那么，也容易想到转移ans[v]=max(dp[v][1],dp2[u][!v][0] + dp[v][1] - 2 * c,dp2[u][!v][1] + dp[v][0] - c)， 其中dp2[u][!v][0]表示以u为根节点，不遍历以v且回到u的最大值，dp2[u][!v][1]?表示以u为根节点，不遍历以v且不回到u的最大值。其中dp2可以在dp计算出来后，动态的维护一下。

//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<bitset>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define xx first
#define yy second
#define LL long long
#define MP make_pair
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))

#define lson l,m,rt << 1
#define rson m + 1,r,rt << 1 | 1

using namespace std;

const int maxn = 100100;

LL dp[maxn][2],ans[maxn];

vector<pair<int,int> > G[maxn];

int val[maxn];

void dfs(int u,int fa) {
    dp[u][0] = val[u]; dp[u][1] = 0;
    for(int i = 0; i < G[u].size(); i ++) {
        int v = G[u][i].first,c = G[u][i].second;
        if(v == fa) continue;
        dfs(v,u);
        if(dp[v][0] > c * 2) {
            dp[u][0] += dp[v][0] - c * 2;
            dp[u][1] = max(dp[v][1] - dp[v][0] + c,dp[u][1]);
        }
        else dp[u][1] = max(dp[v][1] - c,dp[u][1]);
    }
    dp[u][1] = dp[u][0] + dp[u][1];
}

void dfs2(int u,int fa,LL dp0,LL dp1) {
    LL mx = 0,mx2 = 0,all = val[u];
    for(int i = 0; i < G[u].size(); i ++) {
        int v = G[u][i].first,c = G[u][i].second;
        if(v == fa) {
            if(dp0 - 2 * c > 0) {
                all += dp0 - 2 * c;
                if(dp1 - dp0 + c >= mx) mx2 = mx,mx = dp1 - dp0 + c;
                else if(dp1 - dp0 + c > mx2) mx2 = dp1 - dp0 + c;
            }
            else {
                if(dp1 - c >= mx) mx2 = mx,mx = dp1 - c;
                else if(dp1 - c > mx2) mx2 = dp1 - c;
            }
        }
        else {
            if(dp[v][0] - 2 * c > 0) {
                all += dp[v][0] - 2 * c;
                if(dp[v][1] - dp[v][0] + c >= mx)
                    mx2 = mx,mx = dp[v][1] - dp[v][0] + c;
                else if(dp[v][1] - dp[v][0] + c > mx2)
                    mx2 = dp[v][1] - dp[v][0] + c;
            }
            else {
                if(dp[v][1] - c >= mx)
                    mx2 = mx,mx = dp[v][1] - c;
                else if(dp[v][1] - c > mx2)
                    mx2 = dp[v][1] - c;
            }
        }
    }
    for(int i = 0; i < G[u].size(); i ++) {
        int v = G[u][i].first,c = G[u][i].second;
        if(v == fa) continue;
        LL add = all,tmp = dp[v][1] - c;
        if(dp[v][0] - 2 * c > 0) {
            add -= (dp[v][0] - 2 * c);
            tmp = dp[v][1] - dp[v][0] + c;
        }
        ans[v] = add + dp[v][1] - 2 * c;
        ans[v] = max(ans[v],dp[v][1]);
        if(tmp == mx) {
            ans[v] = max(ans[v],add + mx2 + dp[v][0] - c);
            dfs2(v,u,add,add + mx2);
        }
        else {
            ans[v] = max(ans[v],add + mx + dp[v][0] - c);
            dfs2(v,add + mx);
        }
    }
}

int main() {
    int T,cas = 1,n;
    scanf("%d",&T);
    while(T --) {
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++) {
            scanf("%d",&val[i]);
            G[i].clear();
        }
        for(int i = 1; i < n; i ++) {
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            G[u].push_back(MP(v,c));
            G[v].push_back(MP(u,c));
        }
        dfs(1,-1);
        ans[1] = dp[1][1];
        dfs2(1,-1,0);
        printf("Case #%d:n",cas ++);
        for(int i = 1; i <= n; i ++)
            printf("%I64dn",ans[i]);
    }
    return 0;
}