Дано дерево из $$$n$$$ вершин. Некоторые вершины дерева — красные, все остальные — синие.
У каждого ребра дерева есть вес — положительное целое число. Обозначим за $$$d(x, y)$$$ расстояние между вершинами $$$x$$$ и $$$y$$$, т. е. сумму весов ребер, принадлежащих простому пути от $$$x$$$ до $$$y$$$.
Для каждой вершины вы должны выбрать целое число $$$v_i$$$. Эти числа должны удовлетворять следующему ограничению: для каждой синей вершины $$$b$$$ и каждой красной вершины $$$r$$$ должно выполняться $$$d(b, r) \ge v_b + v_r$$$.
Вам нужно максимизировать величину $$$\sum \limits_{i=1}^{n} v_i$$$.
Обратите внимание, что значения $$$v_i$$$ не обязательно должны быть положительными.
В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).
Во второй строке заданы $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$). Если $$$i$$$-я вершина — красная, $$$c_i = 1$$$, иначе $$$c_i = 0$$$.
Затем следуют $$$n-1$$$ строк. В каждой из них заданы три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$1 \le w_i \le 10^6$$$; $$$x_i \ne y_i$$$), обозначающих ребро между вершинами $$$x_i$$$ и $$$y_i$$$ с весом $$$w_i$$$. Эти ребра образуют дерево.
Если значение $$$\sum \limits_{i=1}^{n} v_i$$$ может быть сколько угодно большим, выведите Infinity. Иначе, выведите одно целое число — максимальное значение $$$\sum \limits_{i=1}^{n} v_i$$$, которое вы можете получить.
4 1 1 0 0 3 4 50 3 2 100 2 1 100
350
6 0 1 0 1 0 1 1 2 1 1 4 1 1 6 1 6 5 100 6 3 100
203
3 1 1 1 1 2 100 2 3 100
Infinity
В первом примере можно использовать $$$v_1 = 120, v_2 = 20, v_3 = 80, v_4 = 130$$$.
Название |
---|