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

Bi Luo is a magic boy, he also has a migic tree, the tree has NN nodes , in each node , there is a treasure, it's value is V[i]V[i], and for each edge, there is a cost C[i]C[i], which means every time you pass the edge ii , you need to pay C[i]C[i].

You may attention that every V[i]V[i] can be taken only once, but for some C[i]C[i] , you may cost severial times.

Now, Bi Luo define ans[i]ans[i] as the most value can Bi Luo gets if Bi Luo starts at node ii.

Bi Luo is also an excited boy, now he wants to know every ans[i]ans[i], can you help him?

Input

First line is a positive integer T(T≤104)T(T≤104) , represents there are TT test cases.

Four each test：

The first line contain an integer NN(N≤105)(N≤105).

The next line contains NN integers V[i]V[i], which means the treasure’s value of node i(1≤V[i]≤104)i(1≤V[i]≤104).

For the next N−1N−1 lines, each contains three integers u,v,cu,v,c , which means node uu and node vv are connected by an edge, it's cost is c(1≤c≤104)c(1≤c≤104).

You can assume that the sum of NN will not exceed 106106.

Output

For the i-th test case , first output Case #i: in a single line , then output NN lines , for the i-th line , output ans[i]ans[i] in a single line.

Sample Input

Sample Output

Case #1:
15
10
14
9
15

题意：有一颗 n 个顶点的树，给出每个顶点可以获得的金币，以及走每条边需要花费的金币，问从第 i 个点开始走，可以获得的最大价值。

思路：

转自https://www.cnblogs.com/jihe/p/6007339.html

选择一个点作为根，那么每个考虑从每个点走向子树和走向父亲，回来和不回来的最大值，答案就说max(儿子回来+父亲不回来，父亲回来+儿子不回来)，走向儿子的好求，只是走向父亲的难求一些，但是加上一点，就是考虑父亲是不是有必要向当前的儿子走和不回来的儿子是不是该点就好求了（最后一句什么意思我没有看懂）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int head[N];
int val[N], dp[N][2], fa[N][2], p[N], fp[N];
int n, t, tot;

struct Edge {
    int to, next, cost;
}edge[N << 1];

void addedge(int u, int v, int w) {
    edge[++tot].next = head[u];
    edge[tot].to = v;
    edge[tot].cost = w;
    head[u] = tot;
}

void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}

void dfs1(int u, int f) {
    dp[u][0] = dp[u][1] = val[u];
    p[u] = f;
    fp[u] = u;
    for(int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        int w = edge[i].cost;
        if(v == f) continue;
        dfs1(v, u);
        dp[u][1] += max(0, dp[v][0] - 2 * w);
        if(dp[u][1] < dp[u][0] + dp[v][1] - w) {
            fp[u] = v;
            dp[u][1] = dp[u][0] + dp[v][1] - w;
        }
        dp[u][0] += max(0, dp[v][0] - 2 * w);
    }
}

void dfs2(int u, int f, int d) {
    fa[u][0] = fa[u][1] = 0;
    if(dp[u][0] <= 2 * d) {
        fa[u][0] = max(0, fa[f][0] + dp[f][0] - 2 * d);
        fa[u][1] = max(0, fa[f][1] + dp[f][0] - d);
    }
    else {
        fa[u][0] = max(0, fa[f][0] + dp[f][0] - dp[u][0]);
        fa[u][1] = max(0, fa[f][1] + dp[f][0] - dp[u][0] + d);
    }
    if(fp[f] == u) {
        int mx1 = val[f], mx2 = val[f];
        for(int i = head[f]; ~i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].cost;
            if(v == p[f] || v == u) continue;
            mx1 = max(mx1, mx1 + dp[v][0] - 2 * w);
            mx1 = max(mx1, mx2 + dp[v][1] - w);
            mx2 += max(0, dp[v][0] - 2 * w);
        }
        fa[u][1] = max(fa[u][1], mx1 + fa[f][0] - d);
    }
    else {
        if(dp[u][0] >= 2 * d)
            fa[u][1] = max(fa[u][1], fa[f][0] + dp[f][1] - dp[u][0] + d);
        else
            fa[u][1] = max(fa[u][1], fa[f][0] + dp[f][1] - d);
    }
    for(int i = head[u]; ~i; i = edge[i].next) {
        if(edge[i].to != f)
            dfs2(edge[i].to, u, edge[i].cost);
    }
}

int main() {
    int u, v, w, kcase = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &val[i]);
        }
        init();
        for(int i = 1; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dfs1(1, 0);
        dfs2(1, 0, 0);
        printf("Case #%d:\n", ++kcase);
        for(int i = 1; i <= n; ++i)
            printf("%d\n", max(dp[i][0] + fa[i][1], dp[i][1] + fa[i][0]));
    }
	return 0;
}