基环树，也是环套树，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。因此，对基环树的处理大部分就是对树处理和对环处理。显然，难度在于后者。
在基环树中，它可以选择叶子，并删除他们的邻接点并重复该过程，就可以直到剩下环。
解决这类问题一般都是去拆环，变一般树来处理。
题目：COCI2014/2015 Contest#1 D MAFIJA【基环树最大独立点集】 - Tieechal - 博客园 (cnblogs.com)
COCI2014/2015 Contest#1 D MAFIJA（树形DP/贪心）_Paulliant的博客-CSDN博客
最大独立集专题 - TieT - 博客园 (cnblogs.com)
找环可以用并查集来找，然后将它记录下来。
Q1:怎么断环？
利用并查集维护点与点的连通情况，把合并前就已经在同一集合的边记录下来。到时候dfs时，避开这条边即可。
Q2:断环后怎么搞？
断环后就形成了一棵普通的树，直接树形Dp即可（就是上面那道的做法）。但注意，我们记录的断掉的边(u,v)这两者不能同时取杀手。如何较方便的解决？直接分别以u,v为树根dfs两遍即可，最后将max(dp[u][0],dp[v][0])累计到答案（因为可能会有多个连通的块）。
整个算法的时间复杂度为O(N)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
