点分治的一道好题。
首先要把题目的油量限制转化成下面的形式。
考虑一条 \(u\) 到 \(v\) 的路径（注意是有向的），把这条路径抽出来，对点权、边权编一下号：
那么题目要让我们满足的是对于 \(\forall 1\le i<n\)，都有 \(Sa_i-Sw_i\ge 0\)，其中 \(Sa_i,Sb_i\) 分别表示点权、边权的前缀和。
点分治完后，只需要考虑跨顶点的路径，这样一条路径有两段，一段是端点 \(u\) 向上到根节点 \(rt\)，另一段是从根 \(rt\) 向下到端点 \(v\)，那么先分开来看。
先看向下走的吧，如果直接判 \(rt\) 到 \(v\) 的路径合法性是不对的，因为有可能向上走的路径到了 \(rt\) 多出了一些油量 \(last\)，他可以贡献给向下的路径。
那我们需要找到这条路径上的极值，也就是 \(minn=\min Sa_i-Sw_i\)。不难想到，如果剩余的油量加上这个最小值都大于等于 \(0\) 了，说明对于任何一个前缀和之差都满足大于等于 \(0\) 了，这条路径就是合法的。
所以对于向下的路径，保留所有路径，并顺着记录这个最小值。
再来看向上的路径，向上的路径不用管我们之前说的剩余问题了，所以我们只用判断它合不合法，以及剩余油量。
剩余油量很好求出，但是由于路径是从底下往上走到根的，所以我们要维护出到根的前缀的一些信息，来方便我们进行判断。
考虑已经求出了 \(i\) 号节点的信息，现在遍历到了 \(u\)，那么会有以下几种情况。
- \(a_u-w_u<0\)，说明 \(u\) 往上走一下到 \(i\) 就不合法。
- 否则 \(a_u-w_u\ge 0\)，此时这个值相当于剩余油量会贡献到之上的路径判断中，所以我们同样要维护一个最小值。
具体的，最小值的维护形如这样，\(minn_u=\min(minn_i,0)+a_u-w_u\)，什么意思呢，如果 \(minn_i\) 即 \(i\) 之上的最小值都大于 \(0\)，那么最小值一定产生在 \(u\) 到 \(i\) 这条边上，否则就在之前的最小值上，然后 \(a_u-w_u\) 相当于一个剩余油量，会贡献给每一个 \(u\) 到 \(rt\) 的边，所以最小值是加上这个东西。
如果 \(minn_u\ge 0\) 说明 \(u\) 到 \(rt\) 的路径合法，记录一下剩余油量 \(last\)（注意并不等于 \(minn\)），最后就是找向上的剩余油量 \(last\)，以及向下的限制 \(minn\)，\(last+minn\ge 0\) 的对数。
特殊的，是以 \(rt\) 作为起点、终点的路径，特殊处理下，以及在同一个根节点儿子的子树内的，容斥掉就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
typedef long long ll;
int n,tot=1,head[N];
struct edge{int to,next;ll dis;
}e[N<<1];
void add(int from,int to,ll dis){e[++tot]={to,head[from],dis};head[from]=tot;
}
bool vis[N];
int f,g,F,G,siz[N];
ll ans,a[N],down[N],up[N],Down[N],Up[N];
void getsize(int u,int fa){siz[u]=1;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v!=fa&&!vis[v]){getsize(v,u);siz[u]+=siz[v];}}
}
int getroot(int u,int fa){getsize(u,fa);int half=siz[u]>>1;bool flag=false;while(!flag){flag=true;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v!=fa&&!vis[v]&&siz[v]>half){fa=u,u=v,flag=false;break;}}}return u;
}
void dfs1(int u,int fa,ll sa,ll sw,ll minn){ //往下走 rt->vdown[++f]=minn;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v!=fa&&!vis[v]){dfs1(v,u,sa+a[u],sw+e[i].dis,min(minn,(sa+a[u])-(sw+e[i].dis)));}}
}
void dfs2(int u,int fa,ll sa,ll sw,ll minn){ //往上走 v->son(rt)if(minn>=0){up[++g]=sa-sw;}for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v!=fa&&!vis[v]){dfs2(v,u,sa+a[v],sw+e[i].dis,min(minn,0ll)+a[v]-e[i].dis);}}
}
void calc(int u){for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(!vis[v]){ dfs1(v,u,a[u],e[i].dis,a[u]-e[i].dis); //求down dfs2(v,u,a[v],e[i].dis,a[v]-e[i].dis); //求up sort(down+1,down+f+1); for(int j=1;j<=g;j++){ int id=lower_bound(down+1,down+f+1,-up[j])-down;ans-=(f-id+1); //先容斥掉 } for(int j=1;j<=f;j++){Down[++F]=down[j];if(down[j]>=0) ans++; //rt->v}f=0;for(int j=1;j<=g;j++){Up[++G]=up[j];ans++; //v->rt}g=0;}}sort(Down+1,Down+F+1); for(int j=1;j<=G;j++){int id=lower_bound(Down+1,Down+F+1,-Up[j])-Down;ans+=(F-id+1); //跨过顶点 } F=G=0;
}
void solve(int u){vis[u]=1;calc(u);for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(!vis[v]) solve(getroot(v,u));}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1,x,y,z;i<n;i++){cin>>x>>y>>z;add(x,y,z),add(y,x,z);}solve(getroot(1,0));cout<<ans;return 0;
}