题目
分析
点分治+平衡树。
首先，我们很容易想到这里要使用点分治，然后我们可以考虑如何拼接路径。
发现因为这道题这样的话是有方向的，于是可以考虑维护两个数据结构，一个是从这个点出发，一个是在这个点结束。
那么具体怎么维护呢？我们发现对于一条路径是“在这里结束”类型的，它无论结果有多坏，只要记下它在路径上最坏的那一处，那么另外一条和它拼接的就只要能够使得最坏的那一处满足，那么剩下的肯定满足。
而对于“从这里开始”类型的，它就必须是一直满足条件的状态，然后可以统计当前到根的剩下的多余的油，这个是拿去拼接的“资本”。
由于这里的值域很大，我们不能直接树状数组了，于是可以考虑平衡树，这里使用了 (FHQ Treap) 。
那么拼接就很好维护了，但是，我们发现这样的点对是有序的，所以我们在拼接的时候，只需要正着反着都做一遍，答案就统计完了。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;return;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return;
}
#define ll long long
const int N=1e6+5;
const ll INF=1e18+7;
int n,a[N],idx,siz[N],vis[N],To[N],tmp,pool,root,w[N],Cnt,cnt;
ll Ans,path[N],Now;
struct FHQ_Treap{
int siz,key,rs,ls;
ll val;
#define ls(x) t[x].ls
#define rs(x) t[x].rs
#define key(x) t[x].key
#define val(x) t[x].val
#define siz(x) t[x].siz
}t[N];
inline void Update(int x){siz(x)=siz(ls(x))+siz(rs(x))+1;return ;}
inline int NewNode(ll v){int x=++cnt;siz(x)=1,ls(x)=rs(x)=0,key(x)=rand(),val(x)=v;return x;}
void Split(int now,ll k,int &x,int &y){
if(!now) return x=y=0,void();
if(val(now)<=k) x=now,Split(rs(x),k,rs(x),y);
else y=now,Split(ls(y),k,x,ls(y));
Update(now);
return ;
}
int Merge(int x,int y){
if(!x||!y) return x|y;
if(key(x)<=key(y)){rs(x)=Merge(rs(x),y);Update(x);return x;}
else{ls(y)=Merge(x,ls(y));Update(y);return y;}
}
void Insert(ll v){int x,y;Split(root,v,x,y);root=Merge(Merge(x,NewNode(v)),y);return ;}
void Delete(ll v){int x,y,z;Split(root,v-1,x,y);Split(y,v,z,y);root=Merge(Merge(x,Merge(ls(z),rs(z))),y);return ;}
int Query(ll v){
int x,y,z;
Split(root,v-1,x,y);
z=siz(y);
root=Merge(x,y);
return z;
}
bool Vis[N];
int head[N],nex[N],to[N],val[N];
void add(int u,int v,int w){
nex[++idx]=head[u];
to[idx]=v;
val[idx]=w;
head[u]=idx;
return ;
}
int Root,FMax,Size;
void GetRoot(int x){
Vis[x]=true;siz[x]=1;int Max=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y]||Vis[y]) continue;
GetRoot(y);siz[x]+=siz[y];
Max=max(Max,siz[y]);
}
Max=max(Max,Size-siz[x]);
if(Max<FMax) FMax=Max,Root=x;
Vis[x]=false;
return ;
}
void GetPath1(int x,int fa,ll Max,ll now){
Ans+=Query(Max);
for(int i=head[x];i;i=nex[i]){
int v=to[i];
if(v==fa||vis[v]) continue;
GetPath1(v,x,max(Max,now-a[x]+val[i]),now-a[x]+val[i]);
}
}
void GetPath2(int x,int fa,ll Max,ll now){
if(now>=Max) Insert(now),path[++Cnt]=now,Now++;
for(int i=head[x];i;i=nex[i]){
int v=to[i];
if(v==fa||vis[v]) continue;
GetPath2(v,x,max(now,Max),now+a[v]-val[i]);
}
}
void Calc(int x){
tmp=Cnt=Now=0;
for(int i=head[x];i;i=nex[i]){
int v=to[i];
if(vis[v]) continue;
To[++tmp]=v,w[tmp]=val[i];
}
for(int i=1;i<=tmp;i++){
GetPath1(To[i],x,w[i],w[i]);
GetPath2(To[i],x,a[x],a[x]+a[To[i]]-w[i]);
}
while(Cnt) Delete(path[Cnt--]);
Insert(a[x]);
for(int i=tmp;i>=1;i--){
GetPath1(To[i],x,w[i],w[i]);
GetPath2(To[i],x,a[x],a[x]+a[To[i]]-w[i]);
}
while(Cnt) Delete(path[Cnt--]);
Delete(a[x]);
Ans+=Now/2;
return ;
}
void DFS(int x){
Root=0,FMax=Size=siz[x];
GetRoot(x);
Calc(Root);
vis[Root]=true;
for(int i=head[Root];i;i=nex[i]){
int y=to[i];
if(vis[y]) continue;
DFS(y);
}
}
int main(){
read(n);
for(int i=1;i<=n;i++) read(a[i]);
int x,y,z;
for(int i=1;i<n;i++){
read(x),read(y),read(z);
add(x,y,z),add(y,x,z);
}
Root=0,siz[1]=n;
Insert(-(INF)),DFS(1);
write(Ans);
return 0;
}