浅谈基环树（环套树）

本篇随笔简单讲解一下算法竞赛中的基环树。也叫环套树。

一、基环树概念

其实我个人更喜欢叫它基环树。更好理解。

它的标准定义是：具有N个点N条边的连通图。

如果不保证联通，它就会成为基环树森林。

上张图直观理解一下。

这就是一棵基环树。

如果我们把中间那个醒目的环断开任意一条边，它就会成为一棵树，如果我们把这个环全部断掉，就会成为一个森林。

~~啥？树还会害羞么？~~

所谓内向树的定义是每个点有且只有一条出边。也就是这棵树给人的大体感觉是向内的。

所谓外向树的定义是每个点有且只有一条入边。也就是这棵树给人的大题感觉是外向的。

比如上面的基环树，变成内向树就是：

变成外向树就是：

嗯，也就是基环树变成有向图的一种子定义。

根据上面的定义介绍，我们可以感觉到，基环树虽然被单独拿出来讨论，但是其本质上还是一个比较简单且好理解的数据结构之一。所以它只能适当地提升题目难度，并不能说一个树的题变成基环树就大大增强了。

一些经典例题有：

基环树直径、基环树两点之间距离，基环树DP，等。

这些模型的解决通法一般是：

断环成树，然后将若干棵树处理好之后，再考虑环对答案的影响。也就是将环、树分开讨论解决问题。这时，用”环套树“这个名词来形容基环树，很是容易理解。

比如例题：

这道题是基环树DP的题目，在这道题中，我们对每一棵基环树断掉环上的一条边，然后对断开的两个点分别跑树形DP，就可以得到正确的答案。

总的来说，基环树的一种常用处理方式是”断环“。

再比如例题：

IOI2008岛屿

这道题要求基环树的最长链。

基环树的最长链有两种情况：

第一种是在某棵树里，不经过环。

第二种是经过环。

所以我们可以先用一次DFS找出环，在每个环上节点出发处理树上的最长路径，并计算出从根节点最远到达节点距离根节点的距离。显然，如果经过环的话，肯定要经过这个最大的距离。

所以比较即可。

总的来说，基环树的另一种常用处理方式是分类讨论。