Вам задано взвешенное дерево, состоящее из \(n\) вершин. Напомним, что деревом называется связный граф без циклов. Вершины \(u_i\) и \(v_i\) соединены ребром веса \(w_i\).
Определим \(k\)-раскраску дерева как присвоение каждой вершине ровно \(k\) цветов, таким образом, что каждый цвет используется не более двух раз. Считайте, что различных доступных цветов бесконечно много. Назовем ребро насыщенным в \(k\)-раскраске, если его концы имеют хотя бы один общий цвет (т.е. найдется цвет, который присвоен обоим концам ребра).
Так же определим счет \(k\)-раскраски как сумму весов насыщенных ребер.
Вам необходимо найти максимально возможный счет \(k\)-раскраски заданного дерева.
Вам нужно ответить на \(q\) независимых запросов.
Выходные данные
На каждый запрос выведите одно целое число — максимально возможный счет \(k\)-раскраски заданного дерева.
Примечание
Дерево, соответствующее первому запросу в тестовом примере:
Одна из возможных \(k\)-раскрасок в первом запросе: \((1), (1), (2), (2)\), тогда ребра номер \(1\) и \(3\) являются насыщенными и сумма их весов равна \(8\).
Дерево, соответствующее второму запросу в тестовом примере:
Одна из возможных \(k\)-раскрасок во втором запросе: \((1, 2), (1, 3), (2, 4), (5, 6), (7, 8), (3, 4), (5, 6)\), тогда ребра номер \(1\), \(2\), \(5\) и \(6\) являются насыщенными и сумма их весов равна \(14\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 1
1 2 5
3 1 2
3 4 3
7 2
1 2 5
1 3 4
1 4 2
2 5 1
2 6 2
4 7 3
|
8
14
|