CF1681F.Unique Occurrences

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 \lt u \le n$.

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

令 $f(v, u)$ 表示在顶点 $v$ 与 $u$ 之间的简单路径上的边中，恰好出现一次的数值的个数。

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

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.

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

接下来的 $n-1$ 行每行包含三个整数 $v$、$u$ 和 $x$（$1 \le v, u, x \le n$）——一条边的描述：该边所连接的两个顶点，以及边上所写的数值。

给定的边构成一棵树。

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

输出一个整数——对所有满足 $v \lt u$ 的顶点对 $(v, u)$，求 $f(v, u)$ 的总和。