【bzoj1040】骑士
题意
给定一个基环森林，求最大独立集。
分析
其实这是一道一年前做过的题。
只是今天在看bzoj1023的时候突然来了几许兴致，回过头来看一看。
如果对于一棵树的最大独立集，那就是【没有上司的舞会】，也就是一个简单的树形dp。
现在很明显要将其与这道题建立一定的联系。
对于基环森林中的每一棵基环树，我们先找到环。
接下来，就有两种分析思路。
（1）考虑环中的任意一条边\((u,v)\)，在我们的结果中，\((u,v)\)必然会有至少一个点不选。所以我们分开两次枚举\((u,v)\)不选，这样的话\((u,v)\)这条边就等价于没有。所以直接删除\((u,v)\)这条边，分别以\(u\)和\(v\)为根进行两次树形dp，然后取\(max(f[u][0],f[v][0])\)即可。
（2）第一种想法比较巧，能成立是因为有“\((u,v)\)必然会有至少一个点不选”的特性，我们根据这个特性设计了算法。
就算没有发现这一条性质，其实也可以做。
如图，对于一个基环树，它会形成一个环，环中的每个点都镶嵌着一棵子树。
我们先对于每棵子树进行树形dp，然后枚举环的第一棵子树的根有没有，分开两次线性dp下去就可以了。
小结
（1）基环树
回顾一下基环树的一些性质与判定。
表述形式1：\(n\)个点\(n\)条边
表示形式2：\((i,a_i)\)
（2）环处理
环的处理手段还是蛮多的。
①把环上的节点倍增一次
②讨论环上第一个的情况，然后处理
③例如本问题，如果环上任意相邻两个的状态有着某种特性，那么可以直接考虑断开这条边来搞