Nguồn: Tự nghĩ.
Rating : 1900.

**Đề Bài**:

Nauw có một cây gồm $n$ đỉnh và $n-1$ cạnh. Độ đẹp của một cành cây $u, v$ là $h(u, v)$, với $h(u, v)$ là số lượng các trọng số cạnh xuất hiện nhiều hơn 1 lần trong đường đi từ $u$ -> $v$. Độ đẹp của cả cây sẽ bằng tổng độ đẹp của tất cả độ đẹp của các cành cây $h(u, v)$ với mọi $u, v(u < v)$. Hãy tính độ đẹp của cây.

**Input**:
* Dòng đầu chứa số nguyên dương $n$ ($1\le n \le 10^5$) thể hiện số lượng đỉnh.
* $n-1$ dòng tiếp theo mỗi dòng chứa ba số nguyên dương $u, v, w$ ($1\le u, v, w\le n$) thể hiện một cạnh của cây

**Output**:
* In ra một số nguyên dương duy nhất là kết quả của bài.

**Lời Giải:**

Gọi $d(u, v)$ là số lượng cạnh trên đường đi từ $u$ đến $v$.

=> Độ đẹp của cây sẽ là $(d(u, v)-g(u, v))$ với mọi $u, v(u < v)$ và $g(u, v)$ là số lượng trọng số chỉ xuất hiện 1 lần.

Để tính tổng của các $g(u, v)$ ta có thể làm như sau:
Với mỗi số x là trọng số của cạnh bất kì ta sẽ dsu ghép nó với 2 thành phần liên thông khác không chứa x. Rồi từ đó ta làm như ý tưởng chia để tri với 2 thành phần liên thông như thế.
Khi ta ghép đc một cạnh x ta có thể tăng ans lên size1 * size2 là hai cái size của 2 thành phần liên thông ta ghép được.

Rồi ta chỉ cần xét mọi x và làm như đã nói.
Đpt: O($n.logn^2$) để có được độ phức tạp này ta cần sử dụng dsu rollback.

Còn để tính tổng của các d(u, v) ta có thể dp on tree hoặc nhiều cách khác.
Code: https://ideone.com/xOnqiM
Bài này code hơi khó với e, sai mong anh chị bỏ qua :((