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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone
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\) và \(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\) và \(b:\) có một cạnh nối hai nút \(a\) và \(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\) và \(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\) và \(b\): có cạnh nối giữa \(a\) và \(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