← 返回题目列表

AtCoder · otemae2019_i

I. 彼得兰的道路发展

中文机器翻译题面 查看原题

配点: 100 点

問題

在彼得兰 有 N 个城市, 它们的编号最大为1 到 N 。2 有一条道路连接两个方向的城市。 N 书籍可用,i 番目 (1 \leq i \leq N) 道路就是一座城市 A_i 和城市 B_i 已连接。您可以使用多条道路从任何城市前往任何其他城市。

2 城市之间的距离定义为从一个城市到另一个城市必须采取的最少道路数量。 从N 城市出发 如何选择2 城市 \frac{N (N - 1)}{2} 有几种方法,但它们的距离是 2 权力总和 除以 998\,244\,353 求余数。

制約

  • 2 \leq N \leq 500\,000.
  • 1 \leq A_i \leq N (1 \leq i \leq N).
  • 1 \leq B_i \leq N (1 \leq i \leq N).
  • A_i \neq B_i (1 \leq i \leq N).
  • 您可以使用多条道路从任何城市前往任何其他城市。

小課題

  1. (5 点) N \leq 400.
  2. (5 点) N \leq 4\,000.
  3. (30 点) (A_1, B_1) = (A_2, B_2) = (1, 2),A_i \neq 1 (3 \leq i \leq N),B_i \neq 1 (3 \leq i \leq N).
  4. (60 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
\vdots
A_N B_N

出力

距离显示在标准输出上。 除以 2 权力总和 除以 998\,244\,353 后的余数 1 行。


入力例 1

4
1 2
2 3
3 1
1 4

出力例 1

12
  • 都市 1 和城市 2 的距离是 1
  • 都市 1 和城市 3 的距离是 1
  • 都市 1 和城市 4 的距离是 1
  • 都市 2 和城市 3 的距离是 1
  • 都市 2 和城市 4 的距离是 2
  • 都市 3 和城市 4 的距离是 2

,所以距离 2 幂的总和是 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12 。


入力例 2

6
1 2
1 2
6 3
4 3
3 2
5 2

出力例 2

65

入力例 3

10
7 4
9 7
5 8
8 4
3 7
1 9
10 9
4 1
2 5
6 4

出力例 3

384