#P6837. 法

    ID: 6669 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-k-core 剥离树形 DP贡献法度二链压缩Floyd–Warshall一维前缀和

法

题目描述

给定一张有 nn 个顶点、mm 条边的无向连通图。每条边的长度均为 11。求所有无序的不同顶点对之间的最短路长度之和。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行两个整数 x,yx,y,表示顶点 x,yx,y 之间有一条边。顶点编号为 11 到 nn。

输出格式

输出一个整数,表示所有顶点对之间的最短路长度之和。

样例

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

数据范围

  • 对于 20% 的数据,n≤555n\le555。
  • 对于 40% 的数据,n≤5555n\le5555。
  • 30% 的数据满足图为树,50% 的数据满足图为仙人掌。
  • 对于所有数据,2≤n≤1145142\le n\le114514,n−1≤m≤n+233n-1\le m\le n+233。

原题 PDF,含两组样例的图示