题干：

 

题目大意：

给出一棵n个顶点的树，每个点有一个权值，代表商品的售价，树上每一条边上也有一个权值，代表从这条边经过所需要的花费。现在需要你在树上选择两个点，一个作为买入商品的点，一个作为卖出商品的点，当然需要考虑从买入点到卖出点经过边的花费。使得收益最大。允许买入点和卖出点重合，即收益最小值为0。题目虽然没说，但是默认就是只做一次买卖。

解题报告：

  这题方法很多，最容易想到的就是树形dp了。

  dp[cur][0]代表选取该节点及其子孙中任一节点作为起点到达当前节点所要花费的最小代价，dp[cur][1]代表选取该节点及其子孙中任一节点作为终点到达当前节点所能获得的最大收入。对于最终答案，肯定是经过其中一个点，被我们当做是根节点进行dfs的。所以我们枚举这些点，维护一个最大值就可以了。也就是说，对于每个节点，通过dp[cur][1]-dp[cur][0]更新答案取得最优。

这题相当于是找了一个中转点cur，然后对于每一个中转点维护一个最小值和最大值。

或者认为：dp[u][0]表示以u为根的子树中买一本书的最大收益，dp[u][1]表示以u为根的子树中卖一本书的最大收

益。dp[u][0]+dp[u][1]即为在以u为根的子树中选两点的最大收益。注意是收益，所以是 -w。

一个题解：

树形DP，dp[u][0]表示u节点及其子树中，选个节点卖物品，然后走到u扣掉的最小花费，dp[u][10]表示u节点及其子树中，选个节点买物品，然后走到u扣掉的最小花费，然后加起来更新ans,这里可能会想到，要是两种情况取最值得时候是同一个节点呢？假设在u节点的子树中的所有节点（不包括u）中，二者取最大值时都是v节点，

即-w[v]-dis[u,v],w[v]-dis[u,v]最大，现在我们把v与u比较，假设-w[v]-dis[u,v]>=-w[u],则w[v]-dis[u,v]>=w[u]-2*dis[u,v]<w[u],与w[v]-dis[u,v]>w[u]矛盾，也就是说，二者取最大值时，是不同的点，详情见代码。

最长路是这样考虑：

因为我们不知道从哪点出发到哪点终止。因此虚拟一个起点，一个终点，起点连接所有的节点，权值为−v[i]，代表买入的代价。 
所有节点再连向终点，权值为v[i]，代表卖出的收益。每条边的权值置为负，代表走这条路需要花费代价。跑一次最长路即可。

这样同时可以有效利用了 点权只是用了两个，所以可以用最短路（只考虑边权的），而这两个点权，我们放到新构造的边上去，来统一形式。

网络流做法类似。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
typedef pair<int,ll> PIL;
vector<PIL> vv[MAX];
int n;
ll val[MAX];
ll dp[MAX][2];
void dfs(int cur,int rt) {
	int up = vv[cur].size();
	dp[cur][0] = dp[cur][1] = val[cur];
	for(int i = 0; i<up; i++) {
		int v = vv[cur][i].fi;
		ll w = vv[cur][i].se;
		if(v == rt) continue;
		dfs(v,cur);
		dp[cur][0] = min(dp[cur][0],dp[v][0] + w);
		dp[cur][1] = max(dp[cur][1],dp[v][1] - w);
	}
}

int main()
{
	int t; 
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		ll ans = -1;
		for(int i = 1; i<=n; i++) scanf("%lld",val + i),vv[i].clear();
		for(int a,b,c,i = 1; i<=n-1; i++) {
			scanf("%d%d%d",&a,&b,&c);
			vv[a].pb(pm(b,c*1LL));
			vv[b].pb(pm(a,c*1LL));
		}
		dfs(1,-1);
		for(int i = 1; i<=n; i++) ans = max(ans, dp[i][1]-dp[i][0]);
		printf("%lld\n",ans);
	}
	
	return 0 ;
}

AC代码：（费用流）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
#include <iomanip>
using namespace std;
const int MAX = 2e5 + 5;
const int inf = 0x3f3f3f3f;
struct node {
	int to,c,w,ne;
} e[MAX<<2];
int n,m;
int head[MAX],d[MAX],vis[MAX],tot,p[MAX];
void add(int u,int v,int c,int cost=0) {
	e[++tot].to = v;e[tot].c = c;e[tot].w = cost;e[tot].ne = head[u];head[u] = tot;
	e[++tot].to = u;e[tot].c = 0; e[tot].w = -cost;e[tot].ne = head[v];head[v] = tot;
}
bool bfs(int s,int t) {
	for(int i = 0; i<=n; i++) d[i]=inf,vis[i]=0;
	d[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u]; ~i; i=e[i].ne) {
			int j=e[i].to;
			if(e[i].c&&d[j]>d[u]+e[i].w) {
				d[j]=d[u]+e[i].w;
				p[j]=i;
				if(!vis[j])vis[j]=1,q.push(j);
			}
		}
	}
	return d[t]<inf;
}
int MCMF(int s,int t,int &flow) {
	ll ans=0;
	while(bfs(s,t)) {
		int x=t,f=inf;
		while(x!=s) {
			f = min(f,e[p[x]].c),x=e[p[x]^1].to;
		}
		flow += f;
		ans+=1LL*d[t]*f;
		x=t;
		while(x!=s) {
			e[p[x]].c-=f,e[p[x]^1].c+=f;
			x=e[p[x]^1].to;
		}
	}
	return ans;
}
int main() {
	int t;
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		int st=n+1,ed=n+3;
		tot=1;
		memset(head,-1,sizeof(head));
		for(int x,i = 1; i<=n; i++) {
			scanf("%d",&x);
			add(st,i,1,x);
			add(i,n+2,1,-x);
		}
		add(n+2,n+3,1,0);
		for(int u,v,w,i = 1; i<=n-1; i++) {
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,1,w);
			add(v,u,1,w);
		}
		n+=3;
		int ans2=0;
		int ans=MCMF(st,ed,ans2);
		printf("%d\n",-ans);
	}
	return 0 ;
}