hdu 5834 Magic boy Bi Luo with his excited tree (树形dp）

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   #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<string.h> #include<queue> #define min(a,b) ((a)>(b))?(b):(a) using namespace std; #define INF 1e9 int T; int n; int a[120000]; int b,c,d; struct Edge { int to,next,w; Edge(){} Edge(int to,int next,int w):to(to),next(next),w(w){} } edge[2200000]; int head[120000]; int dp1[1200000]; int dp2[1200000]; int p[1200000]; int ans[1200000]; int tot; void add(int u,int v,int w) { edge[tot] = Edge(v,head[u],w); head[u] = tot++; edge[tot] = Edge(u,head[v],w); head[v] = tot++; } void gettree(int u,int fa) { dp1[u] = dp2[u] = a[u]; p[u]=-1; for(int i=head[u];i; i = edge[i].next) { int v = edge[i].to; if(v==fa) continue; gettree(v,u); int tmp1 = max(0,dp1[v] - edge[i].w *2); int tmp2 = max(0,dp2[v] - edge[i].w); if(dp1[u] + tmp2 >= dp2[u] + tmp1) { dp2[u] = dp1[u] + tmp2; p[u] = v; }else dp2[u] = dp2[u] + tmp1; //dp2[u] = max(dp2[u] + tmp1,dp1[u] + tmp2); dp1[u] +=tmp1; } } void getans(int u,int fa,int sum1,int sum2) { ans[u] = max(sum1 + dp2[u],sum2 + dp1[u]); if(sum2 + dp1[u] >= dp2[u] + sum1) { p[u] = fa; } int w1 =dp1[u]+sum1; int w2 =max(dp2[u]+sum1,sum2 + dp1[u]); for(int i=head[u];i!=0 ; i = edge[i].next) { int v = edge[i].to; if(v==fa) continue; if(v==p[u]) { int d1 = sum1+a[u],d2 = sum2+a[u]; for(int j=head[u];j!=0;j = edge[j].next) { int cc = edge[j].to; if(cc==v||cc==fa) continue; int tmp1 = max(0,dp1[cc] - edge[j].w*2); int tmp2 = max(0,dp2[cc] - edge[j].w); d2 = max(d2 + tmp1 ,d1 + tmp2); d1 =d1 + tmp1; } getans(v,u,max(d1-edge[i].w*2,0),max(d2 - edge[i].w,0)); }else { int tmp1 =max(0, w1 - max(0,dp1[v]-edge[i].w*2) - edge[i].w*2); int tmp2 = max(0,w2 - max(0,dp1[v] - edge[i].w*2) -edge[i].w); getans(v,u,tmp1,tmp2); } } } void init() { memset(head,0,sizeof(head)); tot=1; } int main() { int cas=1; scanf("%d",&T); while(T--) { init(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<n;i++) { scanf("%d%d%d",&b,&c,&d); add(b,c,d); } gettree(1,-1); getans(1,-1,0,0); printf("Case #%d:\n",cas++); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); } return 0; }