题意：给一棵n(≤1e5)个结点，n-1条边的带点权和边权(∈[-1e9,1e9])的树，求这棵树上权值和最大的连通块的权值和

这道题的核心是通过分治的思想把求权值和最大的连通块的问题简化，最简单的时候只有一个结点，显然它就是以它为根的子树中权值和最大的连通块，问题就转化为了怎么在合并的时候保持“权值和最大”这一性质。

我们设dp[i]为以i为根的子树中权值和最大的连通块的权值和，很容易想到状态转移方程为dp[i] = max(dp[i],dp[v] + e[v->i].w)（也就是如果以一个点的儿子为根的子树中权值和最大的连通块的权值和加上连接它们的边的边权大于这个点当前记录的以它为根的子树中权值和最大的连通块的权值，那么就可以更新），而每个点都可以直接初始化为它本身的点权，然后在树上dfs找到每个没有后代的结点，以它们为根的子树中权值和最大的连通块显然已经确定了，从这些地方开始转移并不断用当前结点为子树的权值和最大的连通块的权值和尝试更新答案即可

#include <bits/stdc++.h>
#define int long long

using namespace std;

template <typename T> inline T read(){
	T sum = 0;
	int fl = 1,ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int maxn = 4e5 + 5;


bool vis[maxn];
int n,ans = -1e18,cnt = 0;
int dp[maxn],head[maxn * 2];

struct edge{
	int to;
	int next;
	int w;
}e[maxn * 2];

void add_edge(int u,int v,int w){
    cnt++;
    e[cnt].to = v;
	e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int u,int fa){
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v,u);
		if(dp[v] + e[i].w > 0) dp[u] += dp[v] + e[i].w;
	}
	ans = max(ans,dp[u]);
}

signed main(){
	n = read<int>();
	for(int i = 1; i <= n; i++) dp[i] = read<int>();
	int now = n;
	for(int i = 1; i <= n - 1; i++){
		int u,v,w;
		u = read<int>();
		v = read<int>();
		w = read<int>();
		now++;
		dp[now] = w;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	dfs(1,0);
	printf("%lld\n",ans);
	return 0;
}