Phân Tách Trọng Tâm

Buổi 46 — Centroid Decomposition Buổi 52 — Mock Contest Phase 2
Points
50
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved