Задано дерево, состоящее из \(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\).
3 1 2 1 1 3 2
4
3 1 2 2 1 3 2
2
5 1 4 4 1 2 3 3 4 4 4 5 5
14
2 2 1 1
1
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
6000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач