#1530. 数树上块

数树上块

题目描述

给定一棵含有 nn 个节点,编号为 1n1\sim n 的无边权无根树和一个常数 kk,求出这棵树的直径不超过 kk 的非空导出子图数目。

即,需要选出至少一个节点,满足任意两个被选中节点路径上的所有点也必须被选中,且它们的距离不超过 kk,需要求出选点的方案数。

两点之间的距离定义为两点简单路径上的边数,两个方案不同当且仅当存在某个点,在一个方案中被选中,而在另一个方案中未被选中。

只需要输出答案对 998244353998244353 取模的结果。

输入格式

包含 nn 行。

11 行输入两个正整数 n,kn,k,意义见题目描述。

2n2\sim n 行,每行输入两个正整数 u,vu,v,表示节点 u,vu,v 之间有一条边。

输出格式

包含一行,仅一个自然数,表示符合条件的方案数对 998244353998244353 取模的结果。

样例

5 2
1 2
1 3
3 4
3 5
14

数据范围与提示

2020 个测试点。

对于测试点 141\sim 4,满足 n15n\le 15

对于测试点 5105\sim 10,满足 n2×103n\le 2\times 10^3

对于测试点 111211\sim 12,满足 k=n1k=n-1

对于测试点 132013\sim 20,满足 n5×105n\le 5\times 10^5

对于所有数据,满足 1k<n5×1051\le k< n\le 5\times 10^5,保证输入会给出一棵无根树。