CSES - Fixed-Length Paths I | Đường đi độ dài cố định I

Xem PDF



Tác giả:
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây gồm \(n\) nút, nhiệm vụ của bạn là đếm số đường đi riêng biệt có đúng \(k\) cạnh.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(k:\) số nút và độ dài đường đi. Các nút được đánh số \(1,2,…, n.\)
  • Sau đó có \(n − 1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\)\(b:\) có một cạnh nối hai nút \(a\)\(b\).

Output

  • In một số nguyên: số lượng đường đi.

Constraints

  • \(1≤k≤n≤2 \cdot 10^5\)
  • \(1≤a,b≤n\)

Example

Sample Input

5 2
1 2
2 3
3 4
3 5

Sample Output

4

Bình luận


  • 1
    N7hoatt 5:41 p.m. 29 Tháng 8, 2023 đã chỉnh sửa

    Cho một cây gồm \(n\) đỉnh. Hãy đếm số lượng đường đi phân biệt có chính xác \(k\) cạnh.

    Input

    • Dòng đầu tiên gồm số nguyên \(n\)\(k\): số lượng đỉnh độ dài đường đi. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
    • \(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\)\(b\): có cạnh nối giữa \(a\)\(b\).

    Output

    • In ra một số nguyên: số đường đi.

    Constraints

    • \(1\leq k \leq n \leq 2 \times 10^5\).
    • \(1\leq a,b\leq n\).

    Example

    Test

    Input
    5 2
    1 2
    2 3
    3 4
    3 5
    Output
    4
    Note
    1 phản hồi