Задано дерево, состоящее из $$$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
