Задачи
Сумма расстояний
Сумма расстояний
Задано взвешенное дерево из n вершин и n - 1 ребер. Расстоянием между вершинами u и v будем называть вес наименьшего ребра на пути между u и v.
Найдите сумму расстояний между всеми парами вершин дерева.
Входные данные
Первая строка содержит количество вершин в графе n~(2 \le n \le 10^5). Следующие n - 1 строк описывают ребра. Каждая строка содержит три целых числа: номера вершин, соединенных ребром (вершины пронумерованы числами от 1 до n), и вес ребра.
Выходные данные
Выведите сумму расстояний между всеми парами вершин дерева.
Пример
Входные данные #1
3 1 2 1 1 3 3
Выходные данные #1
5
Входные данные #2
5 1 3 7 4 1 2 4 5 5 2 4 3
Выходные данные #2
30