AT_arc217_e [ARC217E] Tree Growing

给定一棵 $N$ 个点的树，顶点编号为 $1$ 到 $N$，第 $i$ 条边 $(1 \le i < N)$ 连接顶点 $u_i$ 和 $v_i$。 对当前树恰好执行 $K$ 次如下操作。第 $k$ 次操作 $(1 \le k \le K)$ 的步骤为： - 从当前树的 $N-2+k$ 条边中均匀随机地选择一条边 $(u,v)$，删除边 $(u,v)$ 并添加点 $N+k$ 与边 $(u,N+k)$ 和 $(v,N+k)$。 显然的，对于 $k=1,2,\ldots,K$，第 $k$ 次操作后树将包含 $N+k$ 个顶点。 求经过 $K$ 次操作后，$\displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j)$ 的期望值，对 $998244353$ 取模。其中 $\text{dist}(i,j)$ 表示树中顶点 $i$ 和 $j$ 之间的距离。 本题多测。在一个测试点内，你需要解决 $T$ 组测试数据。

第一行一个正整数 $T$ 表示数据组数。 对于每组数据：第一行两个正整数 $N,K$。接下来 $N-1$ 行，每行两个正整数 $u_i,v_i$，表示第 $i$ 条边连接点 $u_i$ 和 $v_i$。

共 $T$ 行，对于每组数据，输出一行一个整数表示答案。

### 样例解释 对于第一组数据，一个例子是： - 第一次操作：选择边 $(1,2)$ 并删除，然后添加边 $(1,5)$ 和 $(2,5)$。 - 第二次操作：选择边 $(2,5)$ 并删除，然后添加边 $(2,6)$ 与 $(5,6)$。 此时，$\displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j)$ 的值为 $32$。 在这组数据中，$\displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j)$ 的值有 $\frac{1}{2}$ 的概率是 $31$，有 $\frac{1}{2}$ 的概率是 $32$。 ### 数据范围 - $1 \le T$ - $2 \le N$，$\sum N\le 3\times 10^5$ - $1 \le K$，$\sum K\le 10^6$ - $1 \le u_i < v_i \le N$ - 给定的图是一棵树。 - 所有输入值均为整数。