🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Vùng cù lao quê thầy Sơn có ~N~ bến ghe, đánh số từ ~1~ đến ~N~, được nối với nhau bởi ~N - 1~ đoạn kênh. Đoạn kênh thứ ~i~ nối hai bến ~u_i~ và ~v_i~, dài ~w_i~ mét. Từ một bến bất kỳ luôn có thể chèo ghe tới mọi bến khác, và giữa hai bến bất kỳ có đúng một đường đi không quay đầu (nói cách khác, các bến và đoạn kênh tạo thành một cây).

Năm nay thầy Sơn được bà con nhờ chọn tuyến cho hội đua ghe ngo. Một tuyến đua được xác định bởi hai bến khác nhau ~u~ và ~v~: các đội xuất phát ở bến ~u~ và về đích ở bến ~v~ theo đường đi duy nhất giữa chúng (đổi chiều ~u, v~ vẫn là cùng một tuyến). Gọi ~L~ là tổng chiều dài các đoạn kênh trên tuyến và ~D~ là chiều dài đoạn kênh dài nhất trên tuyến.

Kinh nghiệm của thầy Sơn: nếu một đoạn kênh chiếm từ một nửa chiều dài cả tuyến trở lên thì đội nào mạnh nước rút trên đúng đoạn đó gần như chắc thắng, cuộc đua mất hay. Vì vậy thầy gọi một tuyến là cân bằng nếu đoạn dài nhất ngắn hơn hẳn tổng các đoạn còn lại, tức là

~2 \cdot D < L.~

Hãy giúp thầy Sơn đếm xem có bao nhiêu tuyến đua cân bằng.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 2 \times 10^5)~.
• ~N - 1~ dòng tiếp theo, dòng thứ ~i~ 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^9)~. Dữ liệu bảo đảm các đoạn kênh tạo thành một cây.

Kết quả

Một số nguyên duy nhất là số tuyến đua cân bằng (số cặp không thứ tự ~\{u, v\}~, ~u \ne v~, thỏa mãn ~2D < L~).

Giới hạn (Subtask)

• Subtask 1 (~15\%~ số điểm): ~N \le 2000~.
• Subtask 2 (~20\%~ số điểm): mọi ~w_i~ bằng nhau.
• Subtask 3 (~25\%~ số điểm): đoạn kênh thứ ~i~ nối bến ~i~ và bến ~i + 1~ (các bến nằm trên một đường thẳng).
• Subtask 4 (~40\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++: 1,5 giây).

Sample Input 1

6
1 2 3
2 3 4
3 4 2
2 5 5
5 6 1

Sample Output 1

3

Giải thích

Tuyến có ~1~ hoặc ~2~ đoạn kênh không bao giờ cân bằng. Các tuyến có từ ~3~ đoạn trở lên:

• ~\{1, 4\}~: các đoạn ~3, 4, 2~, ~L = 9~, ~D = 4~, ~8 < 9~: cân bằng.
• ~\{4, 5\}~: các đoạn ~2, 4, 5~, ~L = 11~, ~D = 5~, ~10 < 11~: cân bằng.
• ~\{4, 6\}~: các đoạn ~2, 4, 5, 1~, ~L = 12~, ~D = 5~: cân bằng.
• ~\{1, 6\}~: các đoạn ~3, 5, 1~, ~L = 9~, ~D = 5~, ~10 \ge 9~: không cân bằng.
• ~\{3, 6\}~: các đoạn ~4, 5, 1~, ~L = 10~, ~D = 5~, ~10 = 10~: không cân bằng (phải nhỏ hơn hẳn).

Vậy có ~3~ tuyến cân bằng.

Sample Input 2

5
1 2 2
2 3 3
3 4 4
4 5 1

Sample Output 2

2

Giải thích

Hai tuyến cân bằng là ~\{1, 4\}~ (các đoạn ~2, 3, 4~) và ~\{1, 5\}~ (các đoạn ~2, 3, 4, 1~). Tuyến ~\{2, 5\}~ có các đoạn ~3, 4, 1~ với ~2 \cdot 4 = 8 = L~ nên không cân bằng.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).