Tổng Trọng Số Cạnh Cực Đại Trên Mọi Đường Đi
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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.
Community Discussion