Олимпиадный тренинг

Задача . F. Уникальные вхождения


Задано дерево, состоящее из \(n\) вершин. На каждом ребре написано целое число.

Пусть \(f(v, u)\) будет равно количеству значений, которые встречаются ровно один раз на ребрах на простом пути между \(v\) и \(u\).

Посчитайте сумму \(f(v, u)\) по всем парам вершин \(v\) и \(u\), для которых \(1 \le v < u \le n\).

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

В первой строке записано одно целое число \(n\) (\(2 \le n \le 5 \cdot 10^5\)) — количество вершин в дереве.

В каждой из следующих \(n-1\) строк записаны три целых числа \(v, u\) и \(x\) (\(1 \le v, u, x \le n\)) — описание ребра: вершины, которое оно соединяет, и значение, написанное на нем.

Заданные ребра образуют дерево.

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

Выведите одно целое число — сумму \(f(v, u)\) по всем парам вершин \(v\) и \(u\) таким, что \(v < u\).


Примеры
№Входные данныеВыходные данные
1
3
1 2 1
1 3 2
4
2
3
1 2 2
1 3 2
2
3
5
1 4 4
1 2 3
3 4 4
4 5 5
14
4
2
2 1 1
1
5
10
10 2 3
3 8 8
4 8 9
5 8 5
3 10 7
7 8 2
5 6 6
9 3 4
1 6 3
120
Статистика успешных решений по компиляторам
 Кол-во
С++5