Đường Kính Của Cây Có Trọng Số

Algorithms Buổi 65-66 — Mock HSG Trees
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved