唯一出现

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一棵包含 $n$ 个顶点的树，每条边上写有一个整数值。

定义 $f(v,u)$ 为顶点 $v$ 到顶点 $u$ 的简单路径上，出现次数恰好为一次的边权值数量。

计算所有满足 $1\le v<u\le n$ 的顶点对 $(v,u)$ 的 $f(v,u)$ 之和。

输入格式

第一行包含整数 $n$。

接下来 $n-1$ 行，每行包含三个整数 $v,u,x$，表示一条连接 $v,u$、权值为 $x$ 的边。

输出格式

输出一个整数，表示所求总和。

样例输入 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

数据范围

• $2\le n\le5\times10^5$；
• $1\le v,u,x\le n$；
• 所有边构成一棵树。