loj#P3134. 「COCI 2019.2」Transport

「COCI 2019.2」Transport

题目描述

译自 COCI 2018/2019 Contest #5 T5「Transport

某个遥远的国度一共有 NN 个城市,这些城市由恰好 N1N-1 条路径连接,使得所有城市相互连通。每个城市都有且仅有一个加油站。已知每条路径的长度和每个加油站具有的燃料分量。

由于不久前刚经历过能源危机,行业协会想了解目前各个城市之间公路运输的能力。假设长途货车每行驶一公里距离要消耗一单位燃料,货车能够从城市 ii 抵达某个相邻城市 jj 当且仅当货车离开城市 ii 时具有的燃料量大于或等于道路 (i,j)(i,j) 的长度。每当货车抵达一个城市,可以在加油站补充不超过加油站燃料分量的燃料。

假设货车的油箱具有无限容量。请你计算,一共有多少个有序城市对 (A,B)(A,B) 满足,油箱燃料最初为 00 的货车可以从城市 AA 出发经过一些城市抵达城市 BB(货车离开城市 AA 时会加满城市 AA 的加油站燃料数)。

输入格式

第一行,是一个正整数 NN

第二行,是 NN 个正整数 AiA_i,依次表示城市 1N1\sim N 的加油站燃料量。

接下来 N1N-1 行,每行是三个正整数 U,V,WU,V,W,表示存在一条连接城市 UU 和城市 VV 的长度为 WW 公里的道路。

输出格式

一行一个整数,表示满足条件的点对数。

2
3 1
1 2 2
1
5
3 1 2 4 5
1 2 3
3 2 2
4 2 6
5 4 3
5

数据范围与提示

对于 100%100\% 的数据,$1\leq N\leq 10^5, 1\leq U, V\leq N, 1\leq A_i\leq 10^9, 1\leq W\leq 10^9$。