← 返回题目列表

Codeforces · 1681/F

F. 独特的事件

中文机器翻译题面 查看原题

给你一棵树,由 $$$n$$$ 个顶点组成。每条边上都写有一个整数值。

令 $$$f(v, u)$$$ 为在顶点 $$$v$$$ 和 $$$u$$$ 之间的简单路径的边缘上仅出现一次的值的数量。

计算所有顶点对 $$$v$$$ 和 $$$u$$$ 上 $$$f(v, u)$$$ 的总和,使得 $$$1 \le v < u \le n$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — 树中的顶点数。

接下来的 $$$n-1$$$ 行包含三个整数 $$$v、u$$$ 和 $$$x$$$ ($$$1 \le v, u, x \le n$$$) - 边的描述:它连接的顶点及其上写入的值。

给定的边形成一棵树。

输出

打印单个整数 - 所有顶点对 $$$v$$$ 和 $$$u$$$ 上 $$$f(v, u)$$$ 的总和,使得 $$$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