21506번 - Сигнализация 서브태스크다국어

Подземный бункер состоит из $n$ комнат, соединённых $n - 1$ коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты $i$ можно дойти в любую другую комнату $j$. Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами $i$ и $j$ и обозначается $\rho(i, j)$.

Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате $i$, активирует датчик звука в каждой комнате, расстояние до которой не превосходит расстояние $d_i$, определяемое мощностью этой сирены. Другими словами, включение сирены в комнате $i$ автоматически включает сирену во всех комнатах $j$, таких что $\rho(i, j) \leq d_i$. Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.

В случае возникновения чрезвычайной ситуации некоторые сирены необходимо включить вручную, после чего звук от них автоматически включит сирены в других комнатах. Правила безопасности предписывают выбор такого набора сирен для ручного включения, который в конце концов приведёт к автоматическому включению сирен во всех комнатах.

Требуется написать программу, которая определяет минимальное количество сирен в наборе, удовлетворяющем правилам безопасности. 

Первая строка входных данных содержит единственное число $n$ --- количество комнат.

Вторая строка содержит последовательность из $n$ целых чисел $d_i$, $i$-е из них равно максимальному расстоянию, на котором расположенная в комнате $i$ сирена активирует датчики ($0 \leq d_i \leq 10^9$).

Последующие $n - 1$ строк описывают коридоры бункера. В $i$-й из них находятся три целых числа: $u_i$, $v_i$, $l_i$, где $u_i$, $v_i$ --- номера различных комнат, соединённых коридором $i$, а $l_i$ --- длина этого коридора ($1 \leq u_i, v_i \leq n$; $1 \leq l_i \leq 10^9$).

Выходные данные должны состоять из единственного числа --- минимального количества сирен, которые необходимо включить вручную.

• $1 \leq n \leq 300\,000$

В тесте из примера сирена в комнате 4 включает сирену в комнате 5, которая, в свою очередь, включает сирены в комнатах 6 и 7. Сирена в комнате 2 включает сирену в комнате 3. Сирена в комнате 8 включает сирены в комнатах 1, 9 и 10.