← 返回题目列表

AtCoder · gigacode_2019_g

G. 千兆国家的道路状况

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

配点: 100 点

問題文

在千兆国 有 N 个城市,每个城市都有 它的编号为 1, 2, 3, \dots, N 。

一些城市有道路相连。具体来说,M 有路,i 真正的道路是城市 a_i 和 b_i 双向连接。此外,您只需走几条路就可以从任何一个城市到达任何其他城市。

在这里,d(i, j) 「城市」 i 和 j 的距离”,即“城市的距离 i 来自城市 j 是仅通过道路行驶时使用的最少道路数量。

然后一切都不同了 2 城市组 到 (x, y) 的距离 求 d(x, y) 的总和。

制約

  • 1 \leq N \leq 100 \ 000
  • 1 \leq M \leq 100 \ 000
  • N - 1 \leq M \leq N + 777
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i
  • 什么 同样在集合 (u, v) 中,城市 u 和城市 最多有一条道路直接连接 v 。
  • 您可以沿着从任何城市到任何城市的道路。
  • 所有输入均为整数

部分点

该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (9 点) N \leq 100, M \leq 100
  2. (7 点) N \leq 3 \ 000, M \leq 3 \ 000
  3. (12 点) M - N = -1 很满意。
  4. (13 点) M - N = 0 很满意。
  5. (28 点) M - N \leq 7 满意。另外, 关于1 \leq i \leq N-1 ,a_i = i, b_i = i+1 很满意。
  6. (22 点) M - N \leq 77 很满意。
  7. (9 分) 没有其他限制。

入力

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

N M
a_1 b_1
a_2 b_2
: :
a_M b_M

出力

所有城市 x, y 之间的距离 请输出 d(x, y) 的总和。

注意

由于该问题的输入/输出规模较大,建议使用高速输入/输出(例如C++的scanf/printf)。


入力例 1

4 3
1 2
2 3
3 4

出力例 1

10

千兆国拥有以下道路网络。

在这个路网中, 从d(1, 2) = 1, d(1, 3) = 2, d(1, 4) = 3, d(2, 3) = 1, d(2, 4) = 2, d(3, 4) = 1 来看,答案是 1+2+3+1+2+1=10 变为。


入力例 2

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

出力例 2

6

千兆国拥有以下道路网络。

在该路网中,所有城市之间的距离为 你可以用 1 移动,所以答案是 6 变为。


入力例 3

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

出力例 3

72