A15137. Unique Occurrences

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$ .