问题陈述
JAG王国的人民讨厌冗余。 例如,JAG王国中的$N$个城市仅与$N-1$个双向道路相连,这样任何城市都可以通过某些道路到达任何城市。 在这种情况下,从一个城市到另一个城市的路径数量对于所有城市对来说恰好是一条。 这是一个非冗余的路网:)
有一天,你,一名 JAG 王国的公民,决定开车去尽可能多的城市旅行。 您将使用的汽车有一个无限大的油箱,但最初油箱是空的。 汽车的油耗为每1公里1升,即行驶1公里消耗1升汽油。
每个城市只有一个加油站,您可以在$x$城市的加油站为您的汽车供应$g_x$升汽油。 当然,您可以选择在旅行中不去某些加油站。 但你不会在同一个加油站供应两次或多次汽油,因为这是多余的。 王国中的每条道路在两个城市之间都有一段距离:第 $i$ 条道路的距离为 $d_i$ 公里。 当然,你不会两次或更多次经过同一个城市或同一条道路,因为这是多余的。
如果储存的汽油量变为零,汽车将无法移动,因此您的旅行将就此结束。 但是,您可能会担心最初是空的水箱。 不用担心。您可以在王国城市的任何加油站出发。 而且,每条道路都直接连接其两端的加油站(因为无冗余的精神避免了城市中的冗余移动),因此即使你的汽车油箱刚到城市就空了,你也可以给你的车加油。
您的任务是编写一个程序,计算最大城市数量,以便您可以根据非冗余政策旅行。
输入
输入由单个测试用例组成。
$N$
$g_1$ … $g_N$
$a_1$ $b_1$ $d_1$
…
$a_{N-1}$ $b_{N-1}$ $d_{N-1}$
第一行包含一个整数$N$ ($1 \le N \le 100{,}000$),这是JAG王国的城市数量。 第二行包含$N$个整数:其中第$i$个为$g_i$ ($1 \le g_i \le 10{,}000$),表示$i$城市的加油站可以供应的汽油量。 下面的$N-1$行给出了道路信息:其中第$j$行包含$a_j$和$b_j$,这表明第$j$条道路双向连接城市$a_j$和$b_j$($1 \le a_j, b_j \le N$, $a_j \ne b_j$),距离$d_j$ ($1 \le d_j \le 10{,}000$)。 您可以假设王国中的所有城市都由道路连接。
输出
打印在约束下您可以从任何城市前往的最大城市数量,以便每个加油站最多可以供应一次汽油。
示例输入 1
5 5 8 1 3 5 1 2 4 2 3 3 2 4 3 1 5 7
样本输入 1 的输出
4
示例输入 2
2 10 1 1 2 10
样本输入 2 的输出
2
示例输入 3
5 1 3 5 1 1 1 2 5 2 3 3 2 4 3 1 5 5
样本输入 3 的输出
3