Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии можно завершить путь в любой пещере.
Генри отправился в экспедицию в сеть пещер за древними артефактами. Вход в пещеры находится в вершине $$$1$$$, а коридоры между пещерами образуют дерево.
Генри освещает путь магической лампой. Для прохождения $$$i$$$-го коридора лампа расходует $$$w_i$$$ единиц заряда при каждом прохождении.
Однако коридоры пещер крайне неустойчивы. После двух прохождений по одному и тому же коридору его своды становятся слишком хрупкими, и в третий раз воспользоваться этим коридором уже невозможно. Поэтому Генри может пройти по каждому коридору не более двух раз, независимо от направления движения.
В каждой пещере находится артефакт. При первом посещении вершины $$$v$$$ артефакт изменяет заряд лампы на $$$a_v$$$ единиц: некоторые артефакты восстанавливают заряд (для которых $$$a_v \gt 0$$$), а другие оказываются проклятыми и, наоборот, забирают его ($$$a_v \lt 0$$$). Повторное посещение пещеры больше не влияет на заряд лампы.
В начале экспедиции Генри находится в пещере $$$1$$$ и сразу активирует находящийся в ней артефакт. Заряд лампы ни в какой момент не должен становиться отрицательным.
Генри должен посетить все пещеры и собрать все артефакты. После этого в любой пещере он сможет активировать портал и покинуть подземелье, поэтому возвращаться ко входу не требуется.
Определите минимальный начальный заряд лампы, с которым Генри сможет завершить экспедицию.
В первой строке входных данных содержится одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество пещер.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — изменения заряда лампы после первого посещения соответствующих пещер. Обратите внимание, что каждый коридор можно пройти не более двух раз вне зависимости от направления движения.
В следующих $$$n - 1$$$ строках содержатся по три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ $$$(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$$$ — концы $$$i$$$-го коридора и количество заряда, необходимое для его прохождения.
Гарантируется, что коридоры образуют дерево.
В единственной строке выведите одно целое число — минимальный начальный заряд лампы, с которым Генри сможет посетить все пещеры, не допуская отрицательного заряда лампы.
51 10 -2 6 71 2 101 3 23 4 13 5 7
16
42 -90 15 301 2 42 3 51 4 10
87
| Осенний кубок МИФИ 2026 |
|---|
| Закончено |
