Đếm cặp đỉnh có khoảng cách đúng bằng D trên cây

Buổi 46 — Centroid Decomposition Mathematics
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$ (mỗi cạnh có độ dài bằng $1$) và một số nguyên dương $D$. Hãy đếm số lượng cặp đỉnh phân biệt $(u, v)$ với $1 \le u < v \le N$ sao cho khoảng cách giữa $u$ và $v$ trên cây đúng bằng $D$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $D$ ($2 \le N \le 5 \cdot 10^4$, $1 \le D < N$).
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một cạnh của cây.
Dữ liệu ra
  • In ra một số nguyên duy nhất là số cặp đỉnh có khoảng cách đúng bằng $D$.
Ví dụ
Input Output
5 2
1 2
2 3
3 4
2 5
4
Giới hạn
  • $2 \le N \le 5 \cdot 10^4$
  • $1 \le D < N$
Draft saved