Tổng Trọng Số Cạnh Cực Đại Trên Mọi Đường Đi

Buổi 52 — Mock Contest Phase 2 Data-structures Trees
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một cây vô hướng gồm $N$ đỉnh được đánh số từ $1$ đến $N$ và $N-1$ cạnh nối. Cạnh thứ $i$ nối hai đỉnh $u_i, v_i$ và có trọng số nguyên dương $w_i$. Với mỗi cặp đỉnh $(u, v)$ sao cho $1 \le u < v \le N$, ký hiệu $M(u, v)$ là trọng số lớn nhất trong số các cạnh nằm trên đường đi đơn duy nhất từ $u$ đến $v$.

Hãy tính giá trị của tổng: \[\sum_{1 \le u < v \le N} M(u, v)\]

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 10^5$).
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le w_i \le 10^6$).
Dữ liệu ra

In ra một số nguyên duy nhất là tổng cần tìm.

Ví dụ
Input Output
4
1 2 3
2 3 5
2 4 2
23
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved