U68642 长途货车

在某个遥远的国度，一共有 $n$ 个城市，这些城市由恰好 $n-1$ 条路径连接，使得所有城市相互连通。每个城市都有且仅有一个加油站。已知每条路径的长度和每个加油站具有的燃料分量。 由于不久前刚经历过能源危机，行业协会想了解目前各个城市之间公路运输的能力。假设长途货车每行驶一公里距离要消耗 $1$ 单位燃料，货车能够从城市 $i$ 抵达某个相邻城市 $j$ 当且仅当货车离开城市 $i$ 时具有的燃料量大于或等于道路 $(i,j)$ 的长度。每当货车抵达一个城市，可以在加油站补充不超过加油站燃料分量的燃料。 假设货车的油箱具有无限容量。请你计算，一共有多少个有序城市对 $(A,B)$ 满足，油箱燃料最初为 $0$ 的货车可以从城市 $A$ 出发走简单路径抵达城市 $B$ 。（货车离开城市 $A$ 时会加满城市 $A$ 的加油站燃料数）

第一行1个正整数 $n$ 。 第二行 $n$ 个正整数 $A[i]$，依次表示城市的加油站燃料量。 接下来 $n-1$ 行，每行是三个正整数 $u,v,w$ 代表一条边。

输出一个整数，表示答案。

对于100%的数据，$1 ≤ n ≤ 10^5, 1 ≤ u,v ≤ n, 1 ≤ A[i] , w ≤ 10^9$。 子任务1（20pts）：$1 ≤ n ≤ 5000$。 子任务2（30pts）：所有道路构成一条链，即城市 $i$ 和城市 $i+1$ 相邻。 子任务3（50pts）：无特殊限制