Rt.

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define in(x) scanf("%lld",&x)
#define fire signed
#define il inline
il void print(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}
int T=1;
int n;
const int N=1e5+10;
int p[N];
int Max[N],siz[N];
vector<pair<int,int>>v[N];
int vis[N],rt,sum;
void dfs(int x,int fa) {
	Max[x]=false;
	siz[x]=1;
	for(auto xx:v[x]) {
		int to=xx.first;
		if(to==fa||vis[to]) continue;
		dfs(to,x);
		siz[x]+=siz[to];
		Max[x]=max(Max[x],siz[to]);
	}
	Max[x]=max(Max[x],sum-siz[x]);
	if(Max[x]<Max[rt]) rt=x;
}
int a[N],idx,tot,b[N];
int sum1[N],sum2[N];
int res;
void dfs1(int x,int fa,int mx,int mi) {//在a中大于等于b的为答案 
	if(sum1[x]-sum2[x]>=mx) {
		a[++tot]=sum1[x]-sum2[x];
	}
	b[++idx]=mi;
	if(mi>=0) res++;
	for(auto xx:v[x]) {
		int to=xx.first;
		if(to==fa||vis[to]) continue;
		sum1[to]=sum1[x]+p[to];
		sum2[to]=sum2[x]+xx.second;
		dfs1(to,x,max(mx,sum1[x]-sum2[x]),min(mi,sum1[x]-sum2[to]));
	}
}
int q1[N],q2[N],cnt1,cnt2;
void get(int x,int fa) {
	vis[x]=1;
	sum1[x]=p[x];
	sum2[x]=false;
	cnt1=cnt2=false;
	for(auto xx:v[x]) {
		int to=xx.first;
		if(to==fa||vis[to]) continue;
		sum1[to]=sum1[x]+p[to];
		sum2[to]=xx.second;
		dfs1(to,x,sum1[x],sum1[x]-sum2[to]);
		sort(a+1,a+1+tot);
		sort(b+1,b+1+idx);
		int l=1;
		rep1(i,cnt2,1) {
			while(l<=tot&&a[l]+q2[i]-p[x]<0) {
				l++;
			}
			res+=tot-l+1;
		}
		l=1;
		rep1(i,idx,1) {
			while(l<=cnt1&&q1[l]+b[i]-p[x]<0) {
				l++;
			}
			res+=cnt1-l+1;
		}
		res+=tot;
		rep(i,1,tot) q1[++cnt1]=a[i];
		rep(i,1,idx) q2[++cnt2]=b[i];
		sort(q1+1,q1+1+cnt1);
		sort(q2+1,q2+1+cnt2);
		idx=tot=false;
	}
	for(auto xx:v[x]) {
		int to=xx.first;
		if(to==fa||vis[to]) continue;
		rt=false;
		sum=siz[to];
		dfs(to,x);
		get(rt,x);
	}
}
void solve() {
	in(n);
	rep(i,1,n) in(p[i]);
	rep(i,1,n-1) {
		int x,y,z;
		in(x),in(y),in(z);
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	Max[0]=LONG_LONG_MAX;
	rt=false;
	sum=n;
	dfs(1,0);
	get(rt,0);
	cout<<res<<endl;
	return;
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}

如下一份代码，时间复杂度最劣为 $n^2\times log(n)$ 但是这道题却放过了。