(树形DP)最大独立集、最小点覆盖、最小支配集

$\large1.最大独立集$

选出最多的点,使得所有点都是不相邻的

状态表示： $dp_{i,j}$ 表示以 $i$ 为根的树，如果 $j$ 为 $0$ ，表示不选这个点，如果 $j$ 为 $1$ ，表示选这个点

属性： $\text{Max}$

状态计算：

如果当前点 $i$ 不选，那么子节点 $j$ 可以被选或不被选：

$dp_{i,0}=\sum_{k=1}^{n}\max (dp_{j_k,0},dp_{j_k,1})$

如果当前点 $i$ 被选，那么子节点 $j$ 一定不能被选：

$dp_{i,1}=\sum_{k=1}^{n}dp_{j_k,0}$

选出最少的点,覆盖所有的边

状态表示： $dp_{i,j}$ 表示以 $i$ 为根的树，如果 $j$ 为 $0$ ，表示不选这个点，如果 $j$ 为 $1$ ，表示选这个点

属性： $\text{Min}$

状态计算：

如果当前点 $i$ 不选，那么子节点 $j$ 一定被选：

$dp_{i,0}=\sum_{k=1}^{n} dp_{j_k,1}$

如果当前点 $i$ 被选，那么子节点 $j$ 可以被选或者不选：

$dp_{i,1}=\sum_{k=1}^{n} \min (dp_{j_k,0},dp_{j_k,1})$

选出最少的点,使得每个点要么被选、要么被它的相邻点支配

状态表示： $dp_{i,j}$ 表示以 $i$ 为根的树，如果 $j$ 为 $0$ ，表示在点 $i$ 不被支配，且将要被父节点支配，如果 $j$ 为 $1$ ，表示在点 $i$ 不被支配，且将要被子节点支配，如果 $j$ 为 $2$ ，表示在点 $i$ 支配

属性： $\text{Min}$

状态计算：

如果当前点 $i$ 要被父节点支配，那么可以选择子节点或者选择该节点：

$dp_{i,0}=\sum_{k=1}^{n}\min(dp_{j_k,1},dp_{j_k,2})$

如果当前的点 $i$ 要被子节点支配，那么就要枚举是哪个子节点 $j$ 被选的方案最小( $u_k$ 代表子节点的第 $k$ 个子节点)：

$dp_{i,1}= \min( dp_{i,1},dp_{j_k,2}+dp_{i,0}-\sum_{k=1}^{n}\min (dp_{u_k,1},dp_{u_k,2}))$

如果选当前的点 $i$ ，那么子节点 $j$ 被 $i$ 支配，或者选择子节点 $j$ ，或者子节点 $j$ 被子节点的子节点 $u$ 支配：

$dp_{i,2}=\sum_{k=1}^{n}\min(dp_{j_k,0},dp_{j_k,1},dp_{j_k,2})$

参考文献：

AcWing算法提高课