hdu5834 Magic boy Bi Luo with his excited tree（樹形dp）

Magic boy Bi Luo with his excited tree

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 723    Accepted Submission(s): 192

Problem Description

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

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

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

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

Input

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

Four each test：

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

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

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

You can assume that the sum of   N  will not exceed   106 .  

Output

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

Sample Input

1
5
4 1 7 7 7 
1 2 6
1 3 1
2 4 8
3 5 2
        

Sample Output

Case #1:
15
10
14
9
15
        

Author

UESTC  

Source

2016中國大學生程式設計競賽 - 網絡選拔賽

題意：說給一棵樹，點和邊都有權值，經過一點可以加上該點的權值但最多隻加一次，經過邊會減去該邊權值，問從各個點分别出發最多能獲得多少權值。

分析：兩個DFS分别在O(n)處理出兩種資訊，各個結點往其為根的子樹走的資訊和各個結點往父親走的資訊，各個結點就能在O(1)合并這兩個資訊分别得出各個結點的最終資訊。。

參考大神部落格：http://www.cnblogs.com/WABoss/p/5771931.html

#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 1e9;
const int MOD = 1e9+7;
#define ll long long
#define CL(a,b) memset(a,b,sizeof(a))
#define lson (i<<1)
#define rson ((i<<1)|1)
#define N 100010
int gcd(int a,int b){return b?gcd(b,a%b):a;}

struct node
{
    int v,c,next;
}e[N<<1];
int tot,head[N];

void add(int u, int v, int c)
{
    e[tot].v = v;
    e[tot].c = c;
    e[tot].next = head[u];
    head[u] = tot++;
}

int val[N];
int d_down[2][N],d_up[2][N];
///dp_down[0/1][u]：u結點往其為根的子樹走，并且不走回來/走回來，能得到的最大權值
///dp_up[0/1][u]：u結點往其父親向上走，并且不走回來/走回來，能得到的最大權值

void dfs1(int u, int fa)
{
    d_down[0][u] = d_down[1][u] = val[u];
    for(int i=head[u]; i!=-1; i=e[i].next)
    {
        int v = e[i].v;
        if(v == fa) continue;
        dfs1(v, u);
        if(d_down[0][v]-2*e[i].c>0)
            d_down[0][u] += d_down[0][v]-2*e[i].c;
    }
    int mx = 0;
    for(int i=head[u]; i!=-1; i=e[i].next)
    {
        int v = e[i].v;
        if(v == fa) continue;
        if(d_down[0][v]-2*e[i].c>0)
            mx = max(mx, (d_down[1][v]-e[i].c)-(d_down[0][v]-2*e[i].c));
        else mx = max(mx, d_down[1][v]-e[i].c);
    }
    d_down[1][u] = d_down[0][u] + mx;
}

void dfs2(int u, int fa)
{
    int mx1=0,mx2=0,tmp;
    for(int i=head[u]; i!=-1; i=e[i].next)
    {
        int v = e[i].v;
        if(v == fa) continue;
        if(d_down[0][v]-2*e[i].c>0)
            tmp=(d_down[1][v]-e[i].c)-(d_down[0][v]-2*e[i].c);
        else tmp=d_down[1][v]-e[i].c;

        if(mx1<tmp) mx2=mx1, mx1=tmp;
        else if(mx2<tmp) mx2=tmp;
    }

    for(int i=head[u]; i!=-1; i=e[i].next)
    {
        int v = e[i].v;
        if(v == fa) continue;
        int tmp2;
        if(d_down[0][v]-2*e[i].c>0)
            tmp2=d_down[0][u]-(d_down[0][v]-2*e[i].c);
        else tmp2=d_down[0][u];

        int mx=max(d_up[0][u]-2*e[i].c, tmp2-2*e[i].c);
        mx = max(mx, d_up[0][u]+tmp2-2*e[i].c-val[u]);
        d_up[0][v] = val[v]+max(0, mx);

        if(d_down[0][v]-2*e[i].c>0)
        {
            if(mx1==(d_down[1][v]-e[i].c)-(d_down[0][v]-2*e[i].c))
                tmp = d_down[1][u]-(d_down[1][v]-e[i].c)+mx2;
            else tmp = d_down[1][u]-(d_down[0][v]-2*e[i].c);
        }
        else if(d_down[1][v]-e[i].c>0)
        {
            if(mx1==d_down[1][v]-e[i].c)
                tmp = d_down[1][u]-(d_down[1][v]-e[i].c)+mx2;
            else tmp = d_down[1][u];
        }
        else tmp = d_down[1][u];
        mx = max(d_up[1][u]-e[i].c, tmp-e[i].c);
        mx = max(mx, max(d_up[0][u]+tmp-e[i].c-val[u], d_up[1][u]+tmp2-e[i].c-val[u]));
        d_up[1][v] = val[v]+max(0, mx);
        dfs2(v, u);
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1; cas<=T; cas++)
    {
        tot = 0;
        CL(head, -1);
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",val+i);
        int a,b,c;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a, b, c);
            add(b, a, c);
        }
        dfs1(1, 1);
        d_up[0][1] = d_up[1][1] = val[1];
        dfs2(1, 1);
        printf("Case #%d:\n",cas);
        for(int i=1; i<=n; i++)
        {
            printf("%d\n",max(d_up[1][i]+d_down[0][i], d_up[0][i]+d_down[1][i])-val[i]);
        }
    }
    return 0;
}