Unique Occurrences

题意翻译

- 给定一棵 $n$ 个节点的树，每条边有颜色 $c$ 。 - 求 $\sum_{u=1}^{n} \sum_{v=u+1}^{n} f(u,v)$ 。 - 其中 $f(u,v)$ 的意义是点 $u$ 到点 $v$ 的简单路径上**恰好出现一次**的颜色的数量。 - $n\in [2,5\cdot 10^5],c\in [1,n]$ 。 翻译者：蒟蒻君HJT

题目描述

You are given a tree, consisting of $ n $ vertices. Each edge has an integer value written on it. Let $ f(v, u) $ be the number of values that appear exactly once on the edges of a simple path between vertices $ v $ and $ u $ . Calculate the sum of $ f(v, u) $ over all pairs of vertices $ v $ and $ u $ such that $ 1 \le v < u \le n $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 5 \cdot 10^5 $ ) — the number of vertices in the tree. Each of the next $ n-1 $ lines contains three integers $ v, u $ and $ x $ ( $ 1 \le v, u, x \le n $ ) — the description of an edge: the vertices it connects and the value written on it. The given edges form a tree.

输出格式

Print a single integer — the sum of $ f(v, u) $ over all pairs of vertices $ v $ and $ u $ such that $ v < u $ .

输入输出样例

输入样例 #1

3
1 2 1
1 3 2

输出样例 #1

4

输入样例 #2

3
1 2 2
1 3 2

输出样例 #2

2

输入样例 #3

5
1 4 4
1 2 3
3 4 4
4 5 5

输出样例 #3

14

输入样例 #4

2
2 1 1

输出样例 #4

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

输出样例 #5

120