Đường Kính Của Cây Có Trọng Số
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$, mỗi cạnh nối hai đỉnh $u, v$ có trọng số dương $w$. Đường kính của cây là độ dài (tổng trọng số các cạnh) của đường đi đơn dài nhất giữa hai đỉnh bất kỳ trên cây. Hãy tìm đường kính của cây đã cho.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $N$ ($1 \le N \le 10^5$).
- $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là đường kính của cây.
Ví dụ
| Input | Output |
|---|---|
| 5 1 2 3 1 3 4 2 4 5 2 5 2 |
12 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le w \le 10^9$
Community Discussion