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

Đ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 trong khoảng từ $k_{1}$ đến $k_{2}$ cạnh (bao gồm cả hai đầu).

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 ba số nguyên $n$ , $k_{1}$ , $k_{2}$ .

$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 trong đoạn $[k_{1}, k_{2}]$ .

Ràng buộc

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

Ví dụ

Input	Output	Giải thích
5 2 3 1 2 2 3 3 4 3 5	6	Đường đi độ dài 2: (1,2,3),(2,3,4),(2,3,5),(4,3,5). Độ dài 3: (1,2,3,4),(1,2,3,5). Tổng: 6.
10 2 4 1 2 2 3 2 4 2 5 1 6 6 7 6 8 7 9 7 10	30	Đếm tất cả đường đi có độ dài từ 2 đến 4.

Bình luận

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