DISTTREE - Khoảng cách trong cây
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: namnguyen123

Cho một cây n đỉnh gồm n - 1 cạnh .

Khoảng cách của 2 nút trong cây là độ dài đường đi ngắn nhất giữa 2 nút này . 

Yêu cầu : Cho cây n đỉnh và số k . Tìm số cặp (u ,v) sao cho khoảng cách giữa hai nút (u , v) đúng bằng k . Chú ý 2 cặp (u , v) và (v , u) là 1 cặp . 

INPUT :

Dòng đầu tiên : Gồm 2 số nguyên n , k ( 1 < n < 50000 , 1 < k < 500 ) . 

n - 1 dòng tiếp theo : Chứa 2 số nguyên u , v ( 1 < u , v < n , u # v ). 

OUTPUT : 

Số nguyên là kết quả của bài toán . 

Ví dụ

  • input
    5 2
    1 2
    2 3
    3 4
    2 5
    output
    4

4 cặp là (1 , 3) , (1 , 5) , (3 , 5) , (2 , 4) .

Back to Top