Cặp đỉnh khoảng cách K

Buổi 78 — Bế giảng Trees
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$ và một số nguyên dương $K$. Khoảng cách giữa hai đỉnh trên cây là số cạnh trên đường đi đơn duy nhất nối giữa chúng.

Hãy đếm số cặp đỉnh không phân biệt thứ tự $(u, v)$ ($1 \le u < v \le N$) có khoảng cách đúng bằng $K$.

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