基环树DP
一些基本概念：
在一棵树上加一条边，就会构成一个环，环上会挂着一些子树。
基环树是只有一个环的仙人掌。
如果基环树的边是有向边，环上的点是p1, p2, p3, ...
则环上的边是p1->p2, p2->p3, ..., pn->p1 或者全部反过来
总之就是环上的边要么全部逆时针要么全部顺时针。
对于挂在环上的子树，如果边从环上的点指向自己，那么这棵树就是外向树；
如果从自己指向环上的点，那么这棵树就是内向树。
由若干棵基环树构成的森林，就是基环树森林。
由若干棵内向树构成的森林，就是内向树森林。
由若干棵外向树构成的森林，就是外向树森林。
一些结论：
-
基环树有n个点，n条边，即基环树的边数等于点数。（一个图有n个点，n条边，不一定是基环树，因为图不一定连通）
-
基环树（森林）的判定：每个点x都有一条从x出发的边或者有一条到x的边（有向图）；每个点都连了一条到其它点的边（无向图）。
思路1：断开环上的一条边u->v，使之成为一棵树。
- 边
u->v限制了点的状态。
强制在树形DP的过程中，将被限制了状态（比如是x）的点的状态限制（比如限制成x）。
这样子DP所囊括的所有方案，加上这条边之后，都是满足边u->v的限制的，都一一对应了一个原图中、被u->v限制的方案。
- 边
u->v对于点的状态没有限制。
将这条边删去之后的图，没有这条边，自然也就没有这条边的限制，直接做一遍树形DP即可。
思路2：讨论方案是否经过了环上的点。
- 没有经过环上的点。
对挂在环上的树分别做一次树形DP，就可以求得答案了。
- 经过了环上的点，这时可以将方案分为：挂在环上的树1、环的一部分、挂在环上的树2。
树1和树2可以用树形DP先预处理好，对于环上的一部分，破环成链（就是倍增一次区间）。
然后对于这个区间做DP就行了，接着就是运用线性DP的一些常见套路，比如单调队列优化啥的。
总的来说，就是先考虑这个问题在树上的做法，然后扩展到基环树的情况。
找环一般用Tarjan。
-
358. 岛屿 思路1难以优化复杂度，考虑思路2。路径没有经过环，就是求树的直径；经过了环，将环上的路径记为从x顺时针走到y，因为要最大值，所以这种情况就是
dist(x,y)+d(x)+d(y)，d(x)表示x往子树走最大的路径。对于dist(x,y)，本来是要取较大的半圈，但是如果x顺时针到y是较小的半圈，当枚举到x2=y，y2=x时，就可以枚举到较大半圈的情况了，所以不需要特殊处理。 -
359. 创世纪 同样用思路1即可。这里有一个细节：至少有一个儿子不选，可以转化成有一个儿子一定不选（其它儿子随意）。
这是为什么呢？至少有一个儿子不选的方案，随便将一个没选的儿子作为一定不选，都是有一个儿子一定不选的一种方案。
有一个儿子一定不选的方案，那么至少有一个儿子没选，就是至少有一个儿子不选的方案。
也就是A：至少有一个儿子不选，B：有一个儿子一定不选。
每个A方案都对应了若干了B方案（具体来说，A中没选的儿子数为x，则对应x个B方案），每个B方案对应了唯一的A方案。
需要统计的答案是选中的节点数，所以同一A方案对应的所有B方案的答案都是一样的，对于需要统计的答案，AB是等价的。
也就是1 2 3和1 1 1 1 2 2 2 3 3 3 3的值域都是一致的。
所以可以这样转化。
注意事项：内向树一般要建反边转成外向树（这样才能遍历到所有点），此时要根据题意得出反转后的边的意义。
标签：方案,进阶,不选,笔记,儿子,基环树,算法,DP,环上 From： https://www.cnblogs.com/zhangchenxin/p/17705822.html