坚船利炮

Problem Description

你是一名舰长，你的战舰由 $n$ 个舱室组成，并另有 $n-1$ 条通道，每条通道连接一对舱室；通过若干通道，任意一对舱室都互相可达（可以将战舰看作一棵树）。 在战斗中，由于海浪汹涌，船体颠簸，你和你的敌人都只能大致地瞄准对方：每当你的战舰被击中时，一条未被打断的通道将被打断，且可以认为每条未被打断的通道之间被（选中）打断的概率相等。 一艘战舰的战斗力为所有“ ‘由未被打断的通道连接成的舱室连通块’大小（所含舱室数）的平方”之和。 为了更好地分析局势，请计算当战舰共计被击中 $0 \sim k$ 次时，战舰的期望战斗力——被击中大于 $k$ 次时考虑战舰的战斗力似乎没有什么必要……

Input

第一行含一个正整数 $t ~ (1 \leq t \leq 500)$ ，表示共有多少组询问; 接下来 $t$ 组询问:

• 第一行含三个整数：用于在视觉上分割询问的一个数 $sp=25500$ ，战舰的舱室数 $n ~ (1 \leq n \leq 2 \times 10^5)$ ，和参数 $k ~ (0 \leq k \leq \min (n-1,100))$ ；
• 接下来 $n-1$ 行，第 $i$ 行含两个正整数 $u_i$ 和 $v_i$ $~(1 \leq u_i,v_i \leq n , u_i \neq v_i)$ , 表示第 $i$ 条通道所连两舱室的编号。 保证 $\sum n \leq 10^6$ 。

Output

对每组询问，输出一行 $k+1$ 个非负整数，第 $i$ 个数代表“战舰共计被击中 $i-1$ 次”时战舰的期望战斗力对 $998244353$ 取模后的结果。

Sample Input

2
25500 3 2
1 2
1 3
25500 7 5
2 5
7 1
4 5
4 7
5 6
3 7

Sample Output

9 5 3
49 33 532397011 598946628 133099259 9

Hint

询问2的各答案真实值依次为 $ 49,33,\frac{341}{15},\frac{81}{5},\frac{179}{15},9 $ 。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）