Đường đi độ dài cố định I

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một cây gồm $n$ đỉnh. Hãy đếm số đường đi phân biệt trong cây có độ dài đúng bằng $k$ cạnh.

Hai đường đi được coi là phân biệt nếu chúng khác nhau về tập hợp cạnh sử dụng (tức là đường đi từ $u$ đến $v$ và từ $v$ đến $u$ được tính là một đường đi).

Dữ liệu vào

Dòng đầu gồm hai số nguyên $n$ và $k$ .

$n - 1$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $a$ và $b$ mô tả một cạnh nối đỉnh $a$ và đỉnh $b$ .

Dữ liệu ra

In ra một số nguyên duy nhất là số đường đi có độ dài đúng bằng $k$ cạnh.

Ràng buộc

$1 \leq k \leq n \leq 2 \times 10^{5}$
$1 \leq a, b \leq n$

Ví dụ

Input	Output	Giải thích
5 2 1 2 2 3 3 4 3 5	4	Các đường đi độ dài 2: (1,2,3), (2,3,4), (2,3,5), (4,3,5).
10 3 1 2 2 3 2 4 2 5 1 6 6 7 6 8 7 9 7 10	9	Cây có hai nhánh từ đỉnh 1. Có 9 đường đi độ dài 3.

Bình luận

Không có bình luận tại thời điểm này.