P5306 [COCI 2018/2019 #5] Transport

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

无

无

### 样例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$