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

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.

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