Задача №112822. Сигнализация
Подземный бункер состоит из \(n\) комнат, соединённых \(n − 1\) коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты \(i\) можно дойти в любую другую комнату \(j\). Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами \(i\) и \(j\) и обозначается \(ρ(i, j)\).
Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате \(i\), активирует датчик звука в каждой комнате, рас- стояние до которой не превосходит расстояние \(d_i\) , определяемое мощностью этой сирены. Другими словами, включение сирены в комнате \(i\) автоматически включает сирену во всех комнатах \(j\), таких что \(ρ(i, j) \le d_i\) . Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.
В случае возникновения чрезвычайной ситуации некоторые сирены необходимо включить вручную, после чего звук от них автоматически включит сирены в других комнатах. Правила безопасности предписывают выбор такого набора сирен для ручного включения, который в конце концов приведёт к автоматическому включению сирен во всех комнатах.
Требуется написать программу, которая определяет минимальное количество сирен в наборе, удовлетворяющем правилам безопасности.
Первая строка входных данных содержит единственное число \(n\) — количество комнат.
Вторая строка содержит последовательность из \(n\) целых чисел \(d_i\) , \(i\)-е из них равно максимальному расстоянию, на котором расположенная в комнате \(i\) сирена активирует датчики (\(0 \le d_i \le 10^9\) ).
Последующие n−1 строк описывают коридоры бункера. В \(i\)-й из них находятся три целых числа: \(u_i\) , \(v_i\) , \(l_i\) , где \(u_i\) , \(v_i\) — номера различных комнат, соединённых коридором \(i\), а \(l_i\) — длина этого коридора (\(1 \le u_i , v_i \le n; 1 \le l_i \le 10^9\) ).
Выходные данные должны состоять из единственного числа — минимального количества сирен, которые необходимо включить вручную.
В тесте из примера сирена в комнате 4 включает сирену в комнате 5, которая, в свою очередь, включает сирены в комнатах 6 и 7. Сирена в комнате 2 включает сирену в комнате 3. Сирена в комнате 8 включает сирены в комнатах 1, 9 и 10.
10 1 2 2 2 6 3 4 5 4 3 1 2 5 2 3 1 2 4 5 4 5 2 4 6 4 4 7 3 1 8 1 8 9 5 8 10 4
3