| Codeforces Round 408 (Div. 2) |
|---|
| Закончено |
Несмотря на то, что Инзейн нашел свою кость, его хозяин Зейн еще не вернулся. Чтобы найти Зейна, Инзейну потребуется много денег, которых у него сейчас совсем нет. Чтобы стправиться с этим, он решил взломать банки.
Всего есть n банков, пронумерованных от 1 до n. Банки соединены n - 1 проводами. все банки изначально находятся в состоянии онлайн. У каждого банка есть изначальная защита: защита банка i изначально равна ai.
Определим некоторые понятия перед тем, как продолжить. Банки i и j называются соседними, если и только если между ними существует провод напрямую. Банки i и j называются полу-соседними, если и только если существует такой онлайн банк k, что банки i и k являются соседними, и банки k и j являются соседними.
Когда некоторый банк взломан, он переходит в состояние оффлайн (и никогда не возвращается в онлайн), а другие банки, которые являются соседними или полу-соседними к взломанному, увеличивают свою защиту на 1.
Вначале Инзейн выберет банк, который он взломает первым. Конечно, защита этого банка не должна превышать мощности его компьютера. После этого, он будет выбирать для взлома некоторый банк до тех пор, пока не будут взломаны все банки, но он может выбрать для взлома банк номер x если и только если все следующие условия выполнены:
- Банк x находится в состоянии онлайн. То есть, банк x еще не взломан.
- Банк x является соседним к какому-то оффлайн банку.
- Защита банка x не превосходит мощности компьютера Инзейна.
Определите минимальную необходимую мощность компьютера, с помощью которого Инзейн сможет взломать все банки.
Первая строка содержит одно целое число n (1 ≤ n ≤ 3·105) — число банков.
Вторая строка содержит n целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — защиты банков.
Каждая из следующих n - 1 строк содержит два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), что означает, что есть прямой провод между банками ui и vi.
Гарантируется, что провода соединяют банки так, что Инзейн может взломать все банки, используя компьютер некоторой мощности.
Выведите одно число — минимальная мощность компьютера, с которым Инзейн сможет взломать все банки.
5
1 2 3 4 5
1 2
2 3
3 4
4 5
5
7
38 -29 87 93 39 28 -55
1 2
2 5
3 2
2 4
1 7
7 6
93
5
1 2 7 6 7
1 5
5 3
3 4
2 4
8
В первом примере Инзейн может взломать все банки, используя компьютер мощности 5:
- Изначально защиты банков равны [1, 2, 3, 4, 5].
- Он взламывает банк 5, силы банков становятся равными [1, 2, 4, 5, - ].
- Он взламывает банк 4, силы банков становятся равными [1, 3, 5, - , - ].
- Он взламывает банк 3, силы банков становятся равными [2, 4, - , - , - ].
- Он взламывает банк 2, силы банков становятся равными [3, - , - , - , - ].
- Он взламывает банк 1 и достигает своей цели.
Во втором примере Инзейн может взламывать банки в порядке 4, 2, 3, 1, 5, 7 и 6. Таким образом, ему достаточно компьютера мощностью 93.
