HDU 5834 Magic boy Bi Luo with his excited tree

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
  
  

  
  
   
   Case #1:
15
10
14
9
15
  
  
  
  
   
    
  
  
  
  
   
   一道颇为恶心的树形dp，要考虑的细节挺多的，想了好久死了一堆脑细胞。
  
  
  
  
   
    
  
  
  
  
   
    
  
  
  
  
   
   首先，理解题意以后，我们可以知道，如果要计算从某一个点出发的最优值，可以进行一次dfs
  
  
  
  
   
   以1作为根节点为例，图中我们可以先走1-2在回来2-1在去1-3再到3-5，这样可以得到1 2 3 5四个点的价值减去中间经过的边
  
  
  
  
   
   可以看出一点，从1出发经过很多的分支，最后一条分支是不需要再回来的。
  
  
  
  
   
   所以进行树形dp，需要记录三个值，从这个节点向下每次都回来的最优值g[x]，
  
  
  
  
   
   从这个节点向下最后一次不会来的最优值和次优值dp[x][0]和dp[x][1],顺便记录不会来的是哪一条边f
  
  
  
  
   
   这样，第一次以1为根的dp可以求出dp[1][0]为1节点的答案，接下来通过这个推导下面相邻节点的答案。
  
  
  
  
   
   对于x的某个孩子来说，有两种情况，
  
  
  
  
   
   一种是它向下走不回来，显然这在这在之前的dp中可以得到。
  
  
  
  
   
   另一种是向上走，这就和x节点的最优值选了那条边有关，如果是选择当前边，那么加上之前的次优值，
  
  
  
  
   
   不然就加上之前的最优值，当然要先和0比一下，因为可能不走过去。
  
  
  
  
   
   这样就能推出全部的答案了。
  
  
  
  
   
    
  
  
  
  
   
   
   
   
#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,k) for (int i = j; i >= k; i--)
#define lson x << 1,l,mid
#define rson x << 1 | 1,mid + 1,r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int read()
{
	char ch = getchar();
	while (ch<'0' || ch>'9') ch = getchar();
	int x = ch - '0';
	while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
	return x;
}
int T,n,a[N];
int x,y,z,cas = 0;
int ft[N],nt[N],v[N],u[N],sz;
int g[N],dp[N][2],ans[N][3],f[N][3];

void dfs(int x,int fa)
{
	f[x][0] = f[x][1] = -1;	   g[x] = a[x];
	for (int i = ft[x]; i != -1; i = nt[i])
	{
		if (u[i] == fa) continue;
		dfs(u[i],x);
		g[x] += max(g[u[i]] - 2 * v[i],0);
	}
	for (int i = ft[x]; i != -1; i = nt[i])
	{
		if (u[i] == fa || dp[u[i]][0] <= v[i]) continue;
		int now = g[x] - max(g[u[i]] - 2 * v[i],0) + max(dp[u[i]][0] - v[i],0);
		if (f[x][0] == -1) f[x][0] = i,dp[x][0] = now;
		else if (f[x][1] == -1 || dp[x][1] < now)
		{
			f[x][1] = i;	dp[x][1] = now;
			if (dp[x][0] < dp[x][1]) swap(dp[x][0],dp[x][1]),swap(f[x][0],f[x][1]);
		}
	}
	if (f[x][1] == -1) dp[x][1] = g[x];
	if (f[x][0] == -1) dp[x][0] = g[x];
}

void get(int x,int fa)
{
	for (int i = ft[x]; i != -1; i = nt[i])
	{
		if (u[i] == fa) continue;
		int y = u[i];
		ans[y][0] = dp[y][0] + max(g[x] - max(g[y] - 2 * v[i],0) - 2 * v[i],0);
		ans[y][1] = dp[y][1] + max(g[x] - max(g[y] - 2 * v[i],0);
		f[y][2] = i;
		if (g[y] >= 2 * v[i])
		{
			if (f[x][0] != i) ans[y][2] = ans[x][0] + v[i];
			else ans[y][2] = ans[x][1] + v[i];
		}
		else
		{
			if (f[x][0] != i) ans[y][2] = g[y] - v[i] + ans[x][0];
			else ans[y][2] = ans[x][1] + g[y] - v[i];
		}
		if (ans[y][1] <= ans[y][2]) swap(ans[y][1],ans[y][2]),swap(f[y][1],f[y][2]);
		if (ans[y][0] <= ans[y][1]) swap(ans[y][0],ans[y][1]),swap(f[y][0],f[y][1]);
		g[y] += max(g[x] - max(g[y] - 2 * v[i],0);
		get(u[i],x);
	}
}

int main()
{
	scanf("%d",&T);
	while (T--)
	{
		n = read();    sz = 0;
		rep(i,1,n) a[i] = read(),ft[i] = -1;
		rep(i,n - 1)
		{
			scanf("%d%d%d",&x,&y,&z);
			u[sz] = y;    nt[sz] = ft[x];  v[sz] = z;  ft[x] = sz++;
			u[sz] = x;    nt[sz] = ft[y];  v[sz] = z;  ft[y] = sz++;
		}
		dfs(1,0);
		ans[1][1] = dp[1][1];
		ans[1][0] = dp[1][0];
		get(1,0);
		printf("Case #%d:n",++cas);
		rep(i,n) printf("%dn",ans[i][0]);
	}
	return 0;
}
   
   
  
  
  

（编辑：开发网_开封站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!