Phân Tách Trọng Tâm
Points
50
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho cây gồm N đỉnh, mỗi cạnh có trọng số dương. Đếm số cặp đỉnh (u, v) với u < v sao cho khoảng cách giữa u và v trên cây không vượt quá D.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên N D (1 ≤ N ≤ 100000, 1 ≤ D ≤ 10^9).
N-1 dòng tiếp theo, mỗi dòng chứa ba số nguyên u v w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 10^6) mô tả một cạnh nối u và v với trọng số w.
Dữ liệu ra
In ra số cặp đỉnh thỏa mãn.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n1 2 1\n1 3 2\n2 4 3\n3 5 1 | 4 |
Giới hạn
- 1 ≤ N ≤ 100000
- 1 ≤ D ≤ 10^9
- 1 ≤ w ≤ 10^6
Community Discussion