Subway

题目传送门 前置知识 强连通分量 | 最短路 解法 考虑用 Tarjan 进行缩点，然后跑最短路。 缩点：本题的缩点有些特殊，基于有向图缩点修改而得，因为是无向图，所以在 Tarjan 过程中要额外记录一下从何处转移过来，防止在同一处一直循环。 基环树上找环还有其他方法，这里仅讲解使用 Tarjan ......

题目： In the big cities, the subway systems always look so complex to the visitors. To give you some sense, the following figure shows the map of Beijin ......

[原题](https://codeforces.com/problemset/problem/1060/E) [翻译](https://www.luogu.com.cn/problem/CF1060E) 首先容易想到答案 $ans = \sum_{x\leq y}{\lceil \frac{dist ......

### 题目大意 给定一棵树，每两个有边直接相连的点之间距离为 $1$。现在我们要给所有原来距离为 $2$ 的城市之间修一条长度为 $1$ 的道路。 记 $\operatorname{dis}(a,b)$ 表示 $a,b$ 之间的最短距离，求 $$\sum_{i=1}^n\sum^{n}_{j=i+ ......

[题面](https://codeforces.com/problemset/problem/1060/E) 由题意可知，在原图中经过边数为 $2$ 的一对点，在新图中经过边数为 $1$。所以每对点在新图中的距离为： $$ \begin{aligned} \lceil \frac{dis(i,j)} ......