Задачі
Сумма расстояний
Сумма расстояний
Задано взвешенное дерево из 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