基环树

提示

$n$ 个节点 $n$ 条边构成的无向连通图，即在树上添一条边，这恰好会得到一个环。这样的图称为 “基环树“。

多棵基环树称为 “基环树森林”。

在有向图中，有类似的概念，每个节点有且仅有一条入边的连通有向图，看起来像以 “基环” 为中心，向外扩展的趋势，故称为 “外向图”。如果每条边有且仅有一条出边，这样得到的有向连通图以 “基环” 为中心，向内收缩的趋势，故称为 “内向树”。

求解基环树相关问题的方法，一般都是先找出图中唯一的环，把除了环之外的部分按照按照若干棵树处理，再考虑与环一起计算。

求基环树的直径

基环树的直径有两种情况。

1. 挂在环上某个节点的子树的直径就是基环树的直径。

2. 经过环，且直径的两端分别位于去掉环以后的两棵子树上。

因此，要求出基环树的直径，我们需要预处理出来如下信息：

1. 环，记环上的点分别为 $s_1, s_2, \cdots, s_t$。
2. 对环上的每个点 $s_i$ 在不经过环上其他节点的前提下，进行一次深度优先搜索，按照求树的直径的方法，找到每棵子树的直径并更新答案。同时计算 $D[s_i]$，表示在子树 $s_i$，所能走到的最远距离。

最后，我们处理第二种情况，这相当于在环上找两个不同的点 $s_i$ 和 $s_j$，使得 $D[s_i] + D[s_j] + dist(s_i, s_j)$ 最大，其中 $dist(s_i, s_j)$ 表示 $s_i$ 和 $s_j$ 在环上的距离，有顺时针和逆时针两种情况。采取断环成链的方法，可在 $O(n)$ 的时间复杂度内求的问题的答案。