给你一棵树,由 $$$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