「DROI」Round 1 距离

没有什么距离是无法跨越的。

定义一棵树 $G$ 上两点 $u,v$ 之间的距离 $\operatorname{dis}(u,v)$ 为两点之间点的数量。 若对于树上两点 $u,v$，满足 $\forall x \in G,\operatorname{dis}(u,x) \leq \operatorname{dis}(u,v)$ **且** $\operatorname{dis}(v,x) \leq \operatorname{dis}(u,v)$，那么我们称无序点对 $(u,v)$ 为**极远点对**。 同时，树 $G$ 上一点 $x$ 的权值 $v_x$ 定义为：满足两点间最短路径经过 $x$ 的极远点对的数量。 现给定树 $G$，求 $\sum\limits_{x \in G}{v_x^k}$ 对 $998244353$ 取模的值，其中 $k$ 是给定的常数，且 $k \in [1,2]$。

第一行两个数 $n,k$，分别表示树 $G$ 的点数以及给定的常数。 接下来 $n-1$ 行每行两个整数 $u,v$，表示点 $u$ 和点 $v$ 之间有一条边。

输出一行一个整数，表示答案。

2 1
1 2

2

5 2
1 2
1 3
4 1
5 1

72

#### 样例解释 #1 $(1,2)$ 为极远点对，所以 $1$ 号和 $2$ 号点点权均为 $1$，$1^1 + 1^1 =2$。 ------------ #### 样例解释 #2 极远点对有 $(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$，故答案为 $4 \times 3^2 + 6^2 = 72$。 ------------ #### 数据范围 | 测试点编号 | $1$ | $2$ | $3$ | $4 \sim 5$ | $6$ | $7$ | $8 \sim 9$ | $10$ | | :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: | | $n$ | $300$ | $300$ | $2000$ | $2000$ | $10^5$ | $5 \times 10^6$ | $10^5$ | $5 \times 10^6$| | $k$ | $1$ | $2$ | $1$ | $2$ | $1$ | $1$ | $2$ | $2$ | 对于 $100\%$ 的数据，满足 $n \leq 5 \times 10^6$，$1 \leq k \leq 2$。 **本题输入量较大，请用较快的输入方法。**