Flower_Rainbow_and

题号：NC311650
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\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$ 的路径”上的节点中，距离根节点最远的一个。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示树上节点个数。
此后  行，第  行输入两个整数 ，表示第  条树边连接节点  和 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示所有组合的代价函数  之和对  取模后的结果。

示例1

输入

复制

输出

复制