Đếm cặp đỉnh có khoảng cách đúng bằng D trên cây
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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$
Community Discussion