codeforces#P1681F. Unique Occurrences

    ID: 32959 远端评测题 6000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>data structuresdfs and similardivide and conquerdpdsutrees

Unique Occurrences

Description

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

Input

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.

Output

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

Samples

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