Вам дано корневое дерево, состоящее из \(n\) вершин. Вершины пронумерованы от \(1\) до \(n\), а корнем является вершина \(1\). Также вам дан массив коэффициентов \(s_1, s_2, \ldots, s_n\).
Мультимножество из \(k\) простых путей называется допустимым, если выполняются следующие два условия:
- Каждый путь начинается в вершине \(1\).
- Пусть \(c_i\) — количество путей, покрывающих вершину \(i\). Для каждой пары вершин \((u,v)\) (\(2\le u,v\le n\)), имеющих общего родителя, верно \(|c_u-c_v|\le 1\).
Значение мультимножества путей определяется как
\(\sum\limits_{i=1}^n c_i s_i\).
Можно показать, что всегда можно найти хотя бы одно допустимое мультимножество. Найдите максимальное значение среди всех допустимых мультимножеств.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное значение мультимножества.
Примечание
В первом наборе входных данных одно из оптимальных решений — четыре пути \(1 \to 2 \to 3 \to 5\), \(1 \to 2 \to 3 \to 5\), \(1 \to 4\), \(1 \to 4\), при этом \(c=[4,2,2,2,2]\). Значение будет равно \(4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54\).
Во втором наборе входных данных одно из оптимальных решений — три пути \(1 \to 2 \to 3 \to 5\), \(1 \to 2 \to 3 \to 5\), \(1 \to 4\), при этом \(c=[3,2,2,1,2]\). Значение будет равно \(3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 4
1 2 1 3
6 2 1 5 7
5 3
1 2 1 3
6 6 1 4 10
|
54
56
|