Дано дерево из \(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\) не обязательно должны быть положительными.
Выходные данные
Если значение \(\sum \limits_{i=1}^{n} v_i\) может быть сколько угодно большим, выведите Infinity. Иначе, выведите одно целое число — максимальное значение \(\sum \limits_{i=1}^{n} v_i\), которое вы можете получить.
Примечание
В первом примере можно использовать \(v_1 = 120, v_2 = 20, v_3 = 80, v_4 = 130\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1 0 0
3 4 50
3 2 100
2 1 100
|
350
|
|
2
|
6
0 1 0 1 0 1
1 2 1
1 4 1
1 6 1
6 5 100
6 3 100
|
203
|
|
3
|
3
1 1 1
1 2 100
2 3 100
|
Infinity
|