CF1681F Unique Occurrences

题目描述

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

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

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

输入格式

第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^5$），表示树的顶点数。

接下来的 $n-1$ 行，每行包含三个整数 $v, u, x$（$1 \le v, u, x \le n$），表示一条边连接的两个顶点及其边权值。

给定的边构成一棵树。

输出格式

输出一个整数，表示所有满足 $v < u$ 的顶点对 $(v, u)$ 的 $f(v, u)$ 之和。

输入输出样例 #1

输入 #1

3
1 2 1
1 3 2

输出 #1

4

输入输出样例 #2

输入 #2

3
1 2 2
1 3 2

输出 #2

2

输入输出样例 #3

输入 #3

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

输出 #3

14

输入输出样例 #4

输入 #4

2
2 1 1

输出 #4

1

输入输出样例 #5

输入 #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

说明/提示

由 ChatGPT 4.1 翻译