AT_otemae2019_i.ピーターランドの道路整備 (Road Development in Peterland)

在彼得兰有 $N$ 个城市，这些城市编号从 $1$ 到 $N$。每对城市之间通过双向道路连接，共有 $N$ 条这样的道路。第 $i$ 条道路连接城市 $A_i$ 和 $B_i$（$1 \leq i \leq N$）。任何一个城市都可以通过这些道路到达其他任意城市。

定义两个城市之间的距离为从一个城市到另一个城市所需通过的最小道路数。现需要从这 $N$ 个城市中任意选择两个城市，共有 $\frac{N (N - 1)}{2}$ 种组合方式。求出所有这些组合中的距离的平方和，并对 $998\,244\,353$ 取模，输出结果。

输入数据通过标准输入提供，格式如下：

$N$
$A_1$ $B_1$
$\ldots$
$A_N$ $B_N$

将计算所得的距离平方和对 $998\,244\,353$ 取模后的结果输出在一行中。

• $2 \leq N \leq 500\,000$。
• 对于每个 $i$，$1 \leq A_i, B_i \leq N$ 且 $A_i \neq B_i$。
• 各城市均联通，能通过若干条道路到达其他城市。

子任务

1. ($5$ 分) 当 $N \leq 400$。
2. ($5$ 分) 当 $N \leq 4\,000$。
3. ($30$ 分) 已知 $(A_1, B_1) = (A_2, B_2) = (1, 2)$，且对于 $3 \leq i \leq N$，$A_i, B_i \neq 1$。
4. ($60$ 分) 满足上述所有条件，无其他附加约束。

示例解释

• 城市 $1$ 和城市 $2$ 的距离为 $1$。
• 城市 $1$ 和城市 $3$ 的距离为 $1$。
• 城市 $1$ 和城市 $4$ 的距离为 $1$。
• 城市 $2$ 和城市 $3$ 的距离为 $1$。
• 城市 $2$ 和城市 $4$ 的距离为 $2$。
• 城市 $3$ 和城市 $4$ 的距离为 $2$。

因此，所有距离的平方和为 $1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12$。

本翻译由 AI 自动生成