Вам задано взвешенное дерево, состоящее из \(n\) вершин. Напомним, что деревом называется связный граф без циклов. Вершины \(u_i\) и \(v_i\) соединены ребром веса \(w_i\).
Вам задано \(m\) запросов. \(i\)-й запрос задан целым числом \(q_i\). В этом запросе вам необходимо посчитать количество пар вершин \((u, v)\) (\(u < v\)) таких, что максимальный вес ребра на простом пути между \(u\) и \(v\) не превосходит \(q_i\).
Выходные данные
Выведите \(m\) целых чисел — ответы на запросы. \(i\)-е число должно равняться количеству пар вершин \((u, v)\) (\(u < v\)) таких, что максимальный вес ребра на простом пути между \(u\) и \(v\) не превосходит \(q_i\).
Запросы пронумерованы от \(1\) до \(m\) в порядке входных данных.
Примечание
Картинка, соответствующая дереву из первого тестового примера: 
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 5
1 2 1
3 2 3
2 4 1
4 5 2
5 7 4
3 6 2
5 2 3 4 1
|
21 7 15 21 3
|
|
2
|
1 2
1 2
|
0 0
|
|
3
|
3 3
1 2 1
2 3 2
1 3 2
|
1 3 3
|