HDU 5834 Magic boy Bi Luo with his excited tree

题意：

给出一棵\(n\)个节点的树，树上每一个节点都有一个权值\(v\)，每条边都有一个代价\(w\)，从一个点出发，经过一个点可以得到等同于其点权的收益，经过一个点可以得到等同于其点权的收益，经过一条边可以得到等同于其权值的代价，点权只会获得一次，但是代价会花费多次。
对于每个点，询问从这个点出发，可以得到的最大价值，价值定义为获得点权的收益和减去经过边的代价和。

分析：

首先观察一下答案路径的构成。不难发现对于每个点，答案的路径一定是去若干条链（可以走向父亲），然后回到这个点，只不过最后一次不用走返程。于是我们发现关键点就是这一条不用返程的链。

于是我们可以把答案路径分成两种：

• 1.不用返程的链走向了父亲
• 2.不用返程的链走向了子树内

对于第一种答案，分成两部分：

• 1.在子树内走，最后回到该点
• 2.向子树外走，不用回来

同样的，对于第二种答案：

• 1.向子树外走，最后回到该点
• 2.向子树内走，不用回来

式子就自己推把。

总结：

思路其实很简单，就是麻烦

#include<bits/stdc++.h>
using namespace std;
int n;
int ans[100001];
int a[100001];
int f[100001];//f[i]表示从i出发在i的子树里走一圈最后回到i的最大价值
int g[100001];//g[i]表示从i出发去i的子树里不回来的最大价值
int gg[100001];
//int g1[100001];
int g0[100001];//g0[i]表示使得g[i]最大的子树 
int s[100001];//s[i]表示从i出发，去子树外走一圈的最大价值
int t[100001];//t[i]表示从i出发去i的子树外不回来的最大价值
struct node{
	int to;
	int val;
};

vector<node> v[100001];

void dfs1(int now,int fa){
	for(int i=0;i<v[now].size();i++){
		if(v[now][i].to==fa) continue;
		dfs1(v[now][i].to,now);
		f[now]+=max(0,f[v[now][i].to]-(2*v[now][i].val));		
	}
}

void dfs2(int now,int fa){
	for(int i=0;i<v[now].size();i++){
		if(v[now][i].to==fa) continue;
		dfs2(v[now][i].to,now);
		int tt=(f[now]-max(0,f[v[now][i].to]-2*v[now][i].val)+max(0,g[v[now][i].to]-v[now][i].val));
		if(tt>g[now]){
			//g1[now]=g0[now];
			g0[now]=v[now][i].to;
			gg[now]=g[now];
			g[now]=tt;
		}
		else if(tt>gg[now]){
			gg[now]=tt;
			//g1[now]=v[now][i].to;
		}
	}
}

void dfs3(int now,int fa){
	for(int i=0;i<v[now].size();i++){
		if(v[now][i].to==fa) s[now]=max(s[now],f[fa]-max(0,f[now]-2*v[now][i].val)+s[fa]-2*v[now][i].val);
		else dfs3(v[now][i].to,now);
	}
}

void dfs4(int now,int fa){
	for(int i=0;i<v[now].size();i++){
		if(v[now][i].to==fa){
			t[now]=max(t[now],t[fa]+f[fa]-max(0,f[now]-2*v[now][i].val)-v[now][i].val);
			if(g0[fa]!=now){
				t[now]=max(t[now],g[fa]-max(0,f[now]-2*v[now][i].val)+s[fa]-v[now][i].val);
			}
			else{
				t[now]=max(t[now],gg[fa]-max(0,f[now]-2*v[now][i].val)+s[fa]-v[now][i].val);
			}
			continue;
		}
		else dfs4(v[now][i].to,now);
	}
	ans[now]=max(f[now]+t[now],g[now]+s[now]);
}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i]=a[i];
		g[i]=a[i];
	}
	for(int i=1;i<n;i++){
		int u,vv,w;
		cin>>u>>vv>>w;
		v[u].push_back({vv,w});
		v[vv].push_back({u,w});
	}
	dfs1(1,0);
	dfs2(1,0);
	dfs3(1,0);
	dfs4(1,0);
	/*
	for(int i=1;i<=n;i++) cout<<f[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<g[i]<<" ";
	cout<<endl;
	*/
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}