Unique Occurrences solution codeforces
You are given a tree, consisting of nn vertices. Each edge has an integer value written on it.
Let f(v,u)f(v,u) be the number of values that appear exactly once on the edges of a simple path between vertices vv and uu.
Calculate the sum of f(v,u)f(v,u) over all pairs of vertices vv and uu such that 1≤v<u≤n1≤v<u≤n.
Input
The first line contains a single integer nn (2≤n≤5⋅1052≤n≤5⋅105) — the number of vertices in the tree.
Each of the next n−1n−1 lines contains three integers v,uv,u and xx (1≤v,u,x≤n1≤v,u,x≤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(v,u)f(v,u) over all pairs of vertices vv and uu such that v<uv<u.
Examples
input
Copy
3 1 2 1 1 3 2
output
Copy
4
input
Copy
3 1 2 2 1 3 2
output
Copy
2
input
Copy
5 1 4 4 1 2 3 3 4 4 4 5 5
output
Copy
14
input
Copy
2 2 1 1
output
Copy
1
input
Copy
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
output
Copy
120