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; }