很复杂的图论，据说是最难的 OI 题，我觉得至少是我做过最难的图论题。 以下称层内边为横边，层间边为竖边。 引理 1：每条边是桥的层数是一个前缀（有可能一直是桥）。 我们考虑求出每条边不再是桥的时刻 tim ，有了 tim 之后问题就解决了，因为只需要处理 a =0.9 序列的前缀和即可，注意如果 tim =∞ 根据等比数列求和，它的贡献是 10w 。 引理 2：最多在 O(n) 层之后，所有的边要么一直是桥，要么一直不是桥。 所以我们考虑快速找到每一层有哪些边不再是桥。 从第一层开始，先对第一层横边图进行边双缩点，得到一个边双森林，此时边双内的横边都不会再作为桥了。 接下来考虑将第二层增量地考虑进来。 引理 3：如果在某一个连通块内有两条及以上竖边，那么这些竖边不再是桥。 这个引理没有上面两个平凡，证明如下： 注意到题目保证图连通，所以只看第一层，任意两个连通块一定可以经过第二层及之后的层连通，根据这张图的重复性，第 i 层任意两个连通块一定可以经过 i+1 层及以后的层连通。 假设 x 连向了下一层的 y,z，那么 y,z 一定可以通过之后层到达下一层的 x，所以无论删掉 x→y/z 都不会影响连通性。所以根据引理 3，如果一个连通块出现了两条竖边，那么这两条竖边的出发点 u,v 和边双树上 u,v 路径上所有的边双都在同一个边双内，可以把 u,v 路径上所有边双合并起来，并且这两条竖边的结束点 x,y 间接通过当前及之前的层连通，所以相当于在下一层 x,y 之间加了一条边。 根据上述步骤，最后不断合并边双，直到该连通块所有的竖边从一个边双出发，不妨设这个边双为这个连通块边双树的根。 因为图连通，所以所有连通块至少有一个竖边，因此所有连通块都可以通过上述方法确定根。 考虑给下一层 x,y 加的边。 如果这条边在一个连通块内，那么 x,y 的树上路径和这条边构成了一个环，所以继续把这个环上所有点合并起来。 如果这条边在不同连通块内，这条边合并了这两个连通块，因为每个连通块的根都有一条竖边，所以新连通块有至少两个竖边，继续迭代地进行下去。不断进行上述步骤，直到不再合并连通块为止。 所有边的 tim i 可以在合并边双的时候确定。 实现很复杂，我的实现用一个队列来存储加边事件，为了动态合并边双，使用树上并查集维护所有边双树，因为还要找到树上两点路径，所以可以维护深度，然后类似树剖 LCA 的方法找到这条路径。