题解

思路推导

题目保证每个顶点至多属于一个简单环，因此所有简单环两两点不相交。把每个环看成一个块，把不在环上的顶点看成单点块，再保留块之间的桥，得到的块间结构是一棵树。

在任意合法删边方案中，每个环恰好删除一条边。于是问题的自由度全部集中在各个环上：环外的桥必须保留，而一个环删去一条边后变成一条路径。

先给块树定根。对每个块，令它与父块相连的顶点为块根。对于环块，把环上顶点按顺序记为 $v_0,v_1,\ldots,v_{k-1}$，其中 $v_0$ 是块根。

做法

先用一次非递归深度优先搜索找出所有桥和简单环，并据此建立块树。随后在块树上进行两遍动态规划：后序遍历计算每个块根只向子树方向延伸时的最优高度，前序遍历把父方向和兄弟子块的贡献传给每个顶点。单点块只需维护最大值与次大值；环块则把环复制后使用单调队列求每个起点的最优断边位置。最后将每个顶点向下与向外的贡献取最大值，按原编号输出答案。

自底向上的动态规划

先处理所有子块。对环上或单点块中的顶点 $u$，令 $b_u$ 表示只经过挂在 $u$ 下方的桥边，能够到达的最远顶点距离；没有子块时 $b_u=0$。

考虑一个环块。若在 $v_{t}$ 与 $v_{t+1}$ 之间断开，其中下标按环处理，那么从 $v_0$ 出发，断点一侧的顶点沿正向到达，另一侧的顶点沿反向到达。对固定断点，最坏距离是两个区间最大值的较大者。预处理

$$L_t=\max_{1\le j\le t}(b_{v_j}+j),\qquad R_t=\max_{t\le j<k}(b_{v_j}+k-j),$$

即可在线性时间内枚举断点。环块根向下的最优高度为

$$d_{v_0}=\max\left(b_{v_0},\min_{0\le t<k}\max(L_t,R_{t+1})\right).$$

单点块直接取 $d_u=b_u$。按块树后序处理后，所有块根的向下信息都已得到。

自顶向下换根

令 $f_u$ 表示从 $u$ 离开它自己的向下部分后，在最优删边方案中可能遇到的最坏距离。对于当前环，构造权值

$$a_0=\max(b_{v_0},f_{v_0}),\qquad a_i=d_{v_i}\quad(1\le i<k).$$

现在固定起点 $v_i$。从 $v_i$ 顺时针编号其余顶点，若断点使前 $t$ 个顶点走顺时针方向，其余顶点走逆时针方向，则最坏贡献为

$$F_i(t)=\max\left( \max_{1\le r\le t}(a_{i+r}+r), \max_{t<r<k}(a_{i+r}+k-r) \right),$$

其中环上下标取模。所求的 $f_{v_i}$ 就是所有 $F_i(t)$ 的最小值。

当 $t$ 增大时，第一个最大值单调不减，第二个最大值单调不增，因此最优断点只会出现在两者交叉的位置附近。把环复制三份，并分别维护形如 $a_j-j$ 与 $a_j+j$ 的滑动区间最大值；随着起点顺时针移动，最优断点也不会逆向移动。使用两个单调队列即可让每个位置只进入、离开队列常数次，从而在线性时间内求出整个环上所有非块根顶点的 $f$ 值。

最后处理桥边。对于顶点 $u$ 的某个子块根 $x$，从 $x$ 向外的贡献等于以下三者的最大值再加一：

• $u$ 在当前块另一方向上的贡献；
• $u$ 的父方向贡献 $f_u$；
• $u$ 的其他子块中最大的 $d+1$。

预处理每个顶点所有子块贡献的最大值和次大值，就能对每条桥在常数时间内完成转移。

正确性证明

首先，块间边都是桥，任何生成树都必须保留；每个环若不删边则仍有环，若删去两条或更多边则图不连通，所以每个合法方案在每个环中恰好删去一条边。

自底向上的转移枚举了当前环全部可能的断边位置。固定断点后，环变成一条路径，从块根到任意挂接子结构的距离正好是沿对应方向的环上距离加该位置的向下高度。因此两个区间最大值覆盖了当前块内所有可能的最远点，取断点最小值便得到块根的最优向下高度。

自顶向下时，权值 $a_i$ 已经概括了从环上位置 $i$ 离开当前环后能到达的全部区域。对固定起点和断点，环上每个其他位置恰属于顺时针侧或逆时针侧，公式 $F_i(t)$ 精确计算了该方案的最坏距离。枚举断点等价于枚举该环的全部合法删边方案，因此最小值就是正确的环外贡献。单调队列只加速两个区间最大值和交叉点的查找，不改变候选集合。

桥边转移把父方向、当前块另一方向和兄弟子块三类互不遗漏的区域取最大值。由块树上的后序与前序归纳，每个方向的状态都正确。最终答案 $\max(d_u,f_u)$ 同时覆盖 $u$ 的向下部分与其余部分，所以等于从 $u$ 出发时最优生成树的最小最大叶距。

复杂度分析

每个顶点、每条边和每个环位置只被处理常数次。时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。