Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Полу необходимо собрать фрименов для штурма дома Харконненов. Всего на планете Арракис `N` поселений
фрименов, соединённых между собой `(N-1)` дорогами разной длины.
Пол посылает `M` Наездников Пустыни в разные поселения из поселения с номером 1
с заданием вызвать песчаного червя возле указанного поселения и доставить воинов поселения к дому Харконненов.
Наездники имеют ограниченную выносливость, `i`-й наездник может преодолеть пешком не более `D_i` миль за время, оставшееся до начала штурма.
Из поселения с номером 1 Пол сам доставит воинов и наездников, для которых не нашлось подходящего поселения, вызвав самого большого червя.
Определите максимальное количество поселений, которые будут участвовать в штурме.
Первая строка ввода содержит два целых числа -- количество поселений `N` (`2<=N<=100000`) и количество наездников `M` (`1<=M<=100000`).
Вторая строка ввода содержит `M` целых чисел `D_i` (`1 <= D_i <=10^9`).
Следующие `(N-1)` строка содержат по три целых числа -- номера
поселений `A_j`, `B_j` (`1 <= A_j < B_j <= N`), которые соединяет дорога, и её длина `C_j` (`1<=C_j<=10^4`).
```sample Пример ввода
6 4
100 20 10 50
1 2 10
2 3 20
2 4 30
4 5 40
1 6 60
```
```sample Пример ввода
4
```
Пояснение к примеру: Наездник 1 может добраться до поселения 5, наездник 3 -- до поселения 2, наездник 4 -- до поселения 4,
а наездник 2 -- отправится на штурм вместе с Полом из поселения 1.
Пояснение к задаче: Поселение 1 участвует в штурме всегда, так как для него вызывает червя Пол, не входящий в команду наездников.
Начало
Рабочее место участника
Жадные алгоритмы