P8981 "DROI" Round 1 Distance

No distance is impossible to cross.

Given a tree $G$, define the distance $\operatorname{dis}(u,v)$ between two nodes $u, v$ as the number of nodes on the path between them. If for two nodes $u, v$ on the tree, the following holds: $\forall x \in G,\operatorname{dis}(u,x) \leq \operatorname{dis}(u,v)$ **and** $\operatorname{dis}(v,x) \leq \operatorname{dis}(u,v)$, then we call the unordered pair $(u,v)$ an **extremely far pair**. Also, for a node $x$ in the tree $G$, its weight $v_x$ is defined as: the number of extremely far pairs whose shortest path passes through $x$. Given the tree $G$, compute $\sum\limits_{x \in G}{v_x^k} \bmod 998244353$, where $k$ is a given constant and $k \in [1,2]$.

The first line contains two integers $n, k$, representing the number of nodes in the tree $G$ and the given constant. The next $n - 1$ lines each contain two integers $u, v$, indicating that there is an edge between node $u$ and node $v$.

Output one integer in one line, representing the answer.

#### Sample Explanation #1 $(1,2)$ is an extremely far pair, so the weights of nodes $1$ and $2$ are both $1$, and $1^1 + 1^1 = 2$. ------------ #### Sample Explanation #2 The extremely far pairs are $(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$, so the answer is $4 \times 3^2 + 6^2 = 72$. ------------ #### Constraints | Test Point ID | $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$ | For $100\%$ of the testdata, $n \leq 5 \times 10^6$ and $1 \leq k \leq 2$. **The input size is large, so please use a fast input method.** Translated by ChatGPT 5