## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Unique Occurrences Codeforces Solution | Codeforces Problem Solution 2022

F. Unique Occurrences
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree, consisting of $n$ vertices. Each edge has an integer value written on it.

Let $f\left(v,u\right)$ 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\left(v,u\right)$ over all pairs of vertices $v$ and $u$ such that $1\le v.

Input

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.

Output

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