TLEoj Contest #05 - Đếm cây - TLEOJ: TLE Online Judge

TLEoj Contest #05 - Đếm cây

Điểm: 2300 (thành phần)

Thời gian: 0.5s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

abcdzxzx

Dạng bài

Cho cây không trọng số $N$ đỉnh. Gọi $dist(u,v)$ là độ dài của đường đi đơn từ $u$ đến $v$ trên cây. Đếm số cách chọn một tập $S = \{u_1,u_2,...,u_K\}$ thoả mãn:

$1 \leq u_1<u_2<...<u_K \leq N$
Với mọi bộ chỉ số $(i,j,k)$ $(1 \leq i,j,k \leq K; i \neq j \neq k)$ : $dist(u_i,u_j)+dist(u_j,u_k)>dist(u_i,u_k)$ .

Input, Output và Subtasks

Input

Dòng đầu chứa hai số nguyên $N$ và $K$ $(3 \leq K \leq N \leq 5000)$ .
$N-1$ dòng sau, mỗi dòng chứa $2$ số nguyên dương $u$ , $v$ $(1 \leq u,v \leq N, u \neq v)$ thể hiện một cạnh của cây.

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Output

Ghi một số nguyên duy nhất là số cách chọn thoả mãn. Vì kết quả có thể rất lớn, hãy in ra kết quả chia lấy dư cho $998244353$ .

Subtasks

Subtask 1 $(10\%)$ : $N\le 20$
Subtask 2 $(20\%)$ : $N\le 200$
Subtask 3 $(30\%)$ : $K=3$
Subtask 4 $(40\%)$ : Không có ràng buộc gì thêm

Sample 1

Input

Output

Note

Các tập thỏa mãn: $(1,2,4,5);(1,2,4,6);(1,2,5,6);(1,4,5,6);(2,4,5,6);(2,4,6,7)$

Sample 2

Input

Output

Note

Các tập thỏa mãn: $(1,3,4);(3,4,5)$

Bình luận

Không có bình luận nào.