Задано дерево, состоящее из \(n\) вершин. На каждом ребре написано целое число.
Пусть \(f(v, u)\) будет равно количеству значений, которые встречаются ровно один раз на ребрах на простом пути между \(v\) и \(u\).
Посчитайте сумму \(f(v, u)\) по всем парам вершин \(v\) и \(u\), для которых \(1 \le v < u \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
|