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

Xem PDF
Tác giả:
Flower_On_Stone
Dạng bài
Điểm: 2100 (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ó tối thiểu \(k_1\) và tối đa \(k_2\) cạnh.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n,k_1\) và \(k_2:\) 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_1≤k_2\le n≤2 \cdot 10^5\)
  • \(1≤a,b≤n\)

Example

Sample Input

5 2 3
1 2
2 3
3 4
3 5

Sample Output

6

Bình luận


  • 0
    N7hoatt    5:47 p.m. 29 Tháng 8, 2023

    Cho một cây gồm \(n\) đỉnh. Hãy đếm số lượng đường đi phân biệt có tối thiểu \(k_1\) cạnh và tối đa \(k_2\) cạnh .

    Input

    • Dòng đầu tiên gồm số nguyên \(n\), \(k_1\) và \(k_2\): 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_1 \leq k_2 \leq n\leq 2 \times 10^5\).
    • \(1\leq a,b\leq n\).

    Example

    Test

    Input 
    5 2 3
1 2
2 3
3 4
3 5
    Output 
    6
    Note

    • 1
      nullType    8:19 a.m. 20 Tháng 12, 2022

      The English title is missing an 'I', this should be "Fixed Length Paths II".