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

[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$n$ 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 v$v$ and u$u$.

Solution Click Below:-  CLICK HERE

Calculate the sum of f(v,u)$f(v,u)$ over all pairs of vertices v$v$ and u$u$ such that 1≤v<u≤n$1\le v<u\le n$.

Input

The first line contains a single integer n$n$ (2≤n≤5⋅105$2\le n\le 5\cdot {10}^5$) — the number of vertices in the tree.

Double Sort Codeforces Solution

Game with Cards Codeforces Solution

Card Trick Codeforces Solution

Labyrinth Adventures Codeforces Solution

Unique Occurrences Codeforces Solution

Required Length Codeforces Solution

Each of the next n−1$n-1$ lines contains three integers v,u$v,u$ and x$x$ (1≤v,u,x≤n$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(v,u)$f(v,u)$ over all pairs of vertices v$v$ and u$u$ such that v<u$v<u$.