题意简述
仙人掌上求至少间隔两个位置的最大独立集。
（仙人掌指，没有一条边在两个或以上的环里的无向图。）
题目分析
仙人掌就是树套环，即树上每个结点都是一个结点或环。那么将题目拆解成树上 DP 和环上 DP 即可。用 tarjan 缩点即可。
树上 DP
先来看看树上 DP。
显然每个点有三个状态：不选中且周围有选中、选中、不选中但在选中的点的旁边。记成 \(f[yzh][0/1/2]\)。设 \(xym\) 是 \(yzh\) 的一个孩子。
先来看看 \(f[yzh][0]\)。由于她不选中，且不在一个选中的旁边，可以从孩子的 \(0\)、\(2\) 状态转移而来。
\[f[yzh][0] = \sum \max \Big \lbrace f[xym][0], f[xym][2] \Big \rbrace \]\(f[yzh][1]\)。由于她选中，那么孩子在之前必须没被选中，且不在选中的点的旁边，即只能从孩子的 \(0\) 状态转移而来。注意加上她的价值。
\[f[yzh][1] = \operatorname{val}(yzh) + \sum f[xym][0] \]\(f[yzh][2]\)。她能且只能从一个孩子的 \(1\) 状态转移而来，其他儿子要么是 \(0\) 状态，要么是 \(2\) 状态。取最大值。
\[f[yzh][2] = f[xym'][1] + \sum _ {xym \neq xym'} \max \Big \lbrace f[xym][0], f[xym][2] \Big \rbrace \] 标签：洛谷,题解,sum,SDOI2010,选中,Big,yzh,xym,DP From： https://www.cnblogs.com/XuYueming/p/18300089