[COCI2018-2019#5] Transport

题目描述

一个国家有 $n$ 个城市,每个城市中都有一个加油站,燃料储量为 $a_i$。 有 $n-1$ 条路径,将这些城市连接成一个树形结构。 一个货车能从城市 $u$ 到达城市 $v$ ,货车的燃料量必须不小于 $u,v$ 之间的距离。 每当货车抵达一个城市,就可以补充不超过加油站储量的燃料。 假设货车的油箱是无限大的,请你算出有多少个有序数对 $(u,v)$ 满足: 一个油箱燃料量初始为 $0$ 的货车,可以从城市 $u$ 出发,抵达城市 $v$。 请注意,货车只能走简单路径,也就是说不能走回头路。

输入输出格式

输入格式


第一行一个正整数 $n$。 第二行有 $n$ 个正整数 $a_i$ ,表示每个加油站的燃料储量。 接下来 $n-1$ 行,每行三个正整数 $u,v,w$,表示城市 $u,v$ 之间有一条长为 $w$ 的路径。

输出格式


一行一个整数表示答案。

输入输出样例

输入样例 #1

2
3 1
1 2 2

输出样例 #1

1

输入样例 #2

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

输出样例 #2

5

说明

### 样例1解释: 唯一可行的是 $(1,2)$,即只有 $1\rightarrow 2$ 是可行的。 ### 数据范围: 对于 $20\%$ 的数据: $1\le n \le 5000$ 对于 $40\%$ 的数据: 树是一条链 对于 $100\%$ 的数据: $1\le n \le 10^5$ $1\le u,v \le n$ $1\le w,a_i \le 10^9$