gym102391E

· · 个人记录

问题显然为每个环删掉一条边，所以把每个环独立下来，建出圆方树。

仙人掌的圆方树比较舒服，可以直接在 dfs 树上搞。

一个想法是 f_{u,0} 表示 u 往下拉最长链的最小值，f_{u,1} 表示 u 子树内直径最小值。但是发现这个二元组的数量不少，不太可行，考虑去掉其中一个。

既然 f_{u,1} 就是答案，不妨二分答案，然后在里面一旦直径超过 mid 就直接返回 0。这样就只剩下一个 f_{u} 表示 u 往下拉最长链了。

考虑方点的情况，此时这个方点 $u$ 的定义为，当前的环及其子树处理完后，其父亲 $v$ 的 dp 值。 考虑这玩意怎么求，先是把环拉出来。暴力就是每次删掉一条边，然后枚举每个点算它们的影响。复杂度 $O(n^2)$。 考虑先删掉任意一条边，为了方便，我们假设删掉的这条边使得拉出来的链中，$v$ 在最左边，对于此时的环我们从右往左枚举第 $i$ 条边，意思为删掉第 $i$ 条边，并加入第 $i+1$ 条边。 考虑这玩意的影响，其实就是把最右边的一个点拉出来放到最左边。那么可以在左右维护一个栈，每个位置存栈底到当前位置各种情况的极值即可。 有点难写。 https://codeforces.com/gym/102391/submission/205430874