$\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}$$
$\text{AcWing}$ $285$ 没有上司的舞会(带点权)
$\large 2.最小点覆盖$
选出最少的点,覆盖所有的边
状态表示: $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})$$
$\text{AcWing}$ $323$ 战略游戏(带点权)
$3.最小支配集$
选出最少的点,使得每个点要么被选、要么被它的相邻点支配
状态表示: $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})$$
$\text{AcWing}$ $1077$ 皇宫看守(带点权)
参考文献: