Flower_Rainbow_and_Game_

$\hspace{15pt}$ 有一棵 $n$ 个节点的有根树，树上节点编号从 $1$ 至 $n$ ，树的根节点是 $1$ 。
$\hspace{15pt}$ Rainbow 在点 $u$ ，Flower 在点 $v$ ，定义函数 $\text{dist}(u, v)$ 为点 $u$ 到点 $v$ 的最短距离，即从 $u$ 到 $v$ 需要经过的最短的边数。

$\hspace{15pt}$ Rainbow 想要与 Flower 相遇，相遇的过程需要代价，定义代价函数 $\text{rf}(u, v)$ ，其计算方式如下：
$\hspace{23pt}\bullet\,$ 若 $\text{lca}(u, v) = u$ 或 $\text{lca}(u, v) = v$ ，Rainbow 可以开启传送，直接到达 Flower 的位置，此时代价函数 $\text{rf}(u, v) = 1$ ；
$\hspace{23pt}\bullet\,$ 否则无法开启传送，此时代价函数 $\text{rf}(u, v) = \text{dist}(u, v)$ ，其中 $\text{lca}(u, v)$ 为 $u$ 和 $v$ 的最近公共祖先。

$\hspace{15pt}$ Rainbow 与 Flower 在树上嬉戏，他们体验了各种 $(u, v)$ 组合，但嬉戏的过程中忘记了计算代价函数 $\text{rf}(u, v)$ ，现在请你帮助他们计算所有 $(u, v)$ 的代价。
$\hspace{15pt}$ 由于所有的 $(u, v)$ 组合数量过多，你只需要告诉他们所有组合的代价函数 $\text{rf}(u, v)$ 之和即可。即求解对于所有的 $1 \leq u,v \leq n;\, u < v$ 的 $\text{rf}(u, v)$ 之和：

$\displaystyle\sum\limits_{u=1}^{n - 1}{\sum\limits_{v=u+ 1}^{n} \text{rf}(u, v)}$ 。

$\hspace{15pt}$ 由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

【名词解释】
$\hspace{15pt}$ 最近公共祖先：在一棵有根树中，节点 $u$ 和 $v$ 的最近公共祖先指同时位于“根到 $u$ 的路径”和“根到 $v$ 的路径”上的节点中，距离根节点最远的一个。

$\hspace{15pt}$ 每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^4\right)$ 代表数据组数，每组测试数据描述如下：

$\hspace{15pt}$ 第一行输入一个整数 $n \left(2 \leq n \leq 2 \times 10^5\right)$ ，表示树上节点个数。
$\hspace{15pt}$ 此后 $n - 1$ 行，第 $i$ 行输入两个整数 $u_i, v_i \left(1 \leq u_i, v_i \leq n;\, u_i \neq v_i\right)$ ，表示第 $i$ 条树边连接节点 $u_i$ 和 $v_i$ 。

$\hspace{15pt}$ 除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$ 。

Flower_Rainbow_and_Game

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题