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

?

?

?

?

?

?

?

  
  

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

?

?

  
  

   
   Case #1:
15
10
14
9
15
  
  

?

?

?

?

题意：说给一棵树，点和边都有权值，经过一点可以加上该点的权值但最多只加一次，经过边会减去该边权值，问从各个点分别出发最多能获得多少权值。

分析：两个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,c;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,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("%dn",max(d_up[1][i]+d_down[0][i],d_up[0][i]+d_down[1][i])-val[i]);
        }
    }
    return 0;
}