基环树学习理解

基环树学习理解

定义

基环树是一种特殊的图,我们知道树是由$N$个点,$N - 1$条边组成的,那么我们在树上任意两点之间加上一条边都会产生一个环,我们把这种$N$个点,$N$条边组成的联通无向图称为基环树。如果不保证联通,也可能是基环树森林,注意基环树森林中每个点都必须有一条边连接起来。如果存在独立的点的话,那么很可能其中的一个联通子图中存在两个环,而基环树去要求有且只有一个环。

一般的题型

基环树的直径(树上两点之间的距离中的最大值),基环树上的动态规划,基环树两点之间的距离。

一般解题思路

基环树的最大特征就是有且只有一个环。所以我们解题(接下来以求基环树的直径为例)时,一般从环入手,先找到环。其中找环过程可以用$BFS$的拓扑排序或$DFS$遍历。然后我们可以考虑从环上每个节点出发,在不经过环上其他点的情况下处理出这棵子树的最长链以及叶子节点到根节点的最长距离。然后我们知道基环树的直径只可能有两种情况:

  • 1.树上最长链出现在子树中
  • 2.环上两棵子树中的叶子节点到另一棵子树的叶子节点经过环

所以我们只需在环上在进行一遍$dp$把环上的边考虑进来就可以了。