D. Run, Pancake, Run
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тимур решил заняться пробежками по общежитию. Он мотивирует себя блинами. Общежитие состоит из n комнат, некоторые пары из которых соединены переходами длиной 10 метров. Общежитие является деревом, то есть для каждой пары комнат существует ровно один путь их соединяющий.

Каждая комната содержит тарелку, в которой находится ровно $$$k$$$ блинов. Каждый переход содержит тарелку, в которой находится ровно 2 блина.

Пробежка Тимура выглядит следующим образом:

  1. Тимур стартует в любой из комнат и ест в ней 1 блин. Переходит к шагу 2.
  2. Тимур, находясь в комнате $$$v$$$, выбирает некоторую комнату $$$u$$$, такую, что:
    • Переход между $$$v$$$ и $$$u$$$ существует и содержит хотя бы 1 блин.
    • Комната $$$u$$$ содержит хотя бы 1 блин.
    Если такой комнаты не существует, Тимур расстраивается и немедленно прекращает пробежку. Иначе он переходит к шагу 3.
  3. Тимур перебегает из $$$v$$$ в $$$u$$$, съедая по одному блину в переходе между ними и в комнате $$$u$$$, после чего возвращается к шагу 2.

Тимуру стало интересно, какое максимальное количество метров он сможет пробежать, если выберет стратегию оптимально. Помогите ему определить это.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ $$$(t \le 100)$$$ — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных, разделенные пустой строкой.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$, $$$k$$$ $$$(1 \le n \le 10^5, 1 \le k \le 10^9)$$$.

Следующая $$$n − 1$$$ строка набора тестовых данных содержит два целых числа $$$v$$$, $$$u$$$ $$$(1 \le v, u \le n, u \neq v)$$$ — описание переходов. Гарантируется, что переходы задают дерево.

Гарантируется, что сумма $$$n$$$ в тестовых наборах не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора тестовых данных выведите в отдельной строке одно целое число — ответ на него.

Система оценки
ГруппаБаллыДоп. ограниченияКомментарий
sum$$$_n$$$$$$k$$$
$$$0$$$0——Тесты из условия
$$$1$$$2$$$n \le 1$$$ $$$000$$$$$$k=1$$$
$$$2$$$2—$$$k=1$$$
$$$3$$$3$$$n \le 300$$$$$$k=2$$$
$$$4$$$4$$$n \le 20$$$—
$$$5$$$4$$$n \le 1$$$ $$$000$$$—
$$$6$$$5——

Тесты к этой задаче состоят из 6 групп. Каждый тест в группе оценивается в 1 балл.

Примеры
Входные данные
3
7 1
1 2
1 3
2 4
2 5
3 6
3 7

4 2
1 2
1 3
1 4

2 10
1 2
Выходные данные
40
40
20
Входные данные
1
12 2
7 8
4 5
7 11
8 10
6 7
4 3
9 7
3 2
4 6
1 2
12 11
Выходные данные
160