自下而上树形dp题型详细整理——最大独立集、最小点覆盖、最小支配集

最大独立集

问题特点

选择若干个点，使得没有相邻的两个点均被选择，最大化被选择的点的点权和。简单来说，就是父节点被选了，子节点不能选；父节点没被选，子节点可以选，也可以不选。
转化成图如下，表示其中一种情况，橙色的节点表示被选中。关键在于，父节点没被选，子节点可以选，也可以不选。和第三种类型对比。第三种类型是，父节点没被选，子节点一定得选至少一个。

题目内容

题目链接：https://www.lanqiao.cn/problems/1319/learning/?page=1&first_category_id=1&problem_id=1319

解题思路

设置状态
dp[u][0]：表示u节点不被选择
dp[u][1]：表示u节点被选择
状态转移方程：
假设v1, v2…为u的子节点.

dp[u][0]

u节点不被选择，那么子节点可以被选择，也可以不被选择。
dp[u][0] = max(dp[v1][0], dp[v1][1]) + max(dp[v2][0], dp[v2][1]) + …

dp[u][1]

u节点被选择，那么子节点只能不被选择。
dp[u][1] = dp[v1][0] + dp[v2][0] + …

总结转移方程如下

代码

from collections import defaultdict
# 员工人数
n = int(input())
# 员工快乐指数
a = [0] + list(map(int, input().split()))
# 树
edges = defaultdict(list)
# 找到父节点
fujiedian = set(range(1, n+1))
def add(from_node, to_node):
    edges[from_node].append(to_node)
# 添加边
for _ in range(n-1):
    # v是上司， u是下属
    u, v = map(int, input().split())
    add(v, u)
    fujiedian.discard(u)

fu = fujiedian.pop()
# 不选 选的快乐指数
dp = [[0, a[i]] for i in range(0, n+1)]
def dfs(u):
    for v in edges[u]:
        dfs(v)
        dp[u][0] += max(dp[v])
        dp[u][1] += dp[v][0]
dfs(fu)
print(max(dp[fu]))

最小点覆盖

问题特点

选择若干个点，使得树上的每一条边都被覆盖，即每一条边上至少有一个端点被选择，最小化被选择的点的点权和。
转化为图的情况如下：橙色线表示每一条边都要被选中。

题目内容

找不到题目链接。
输入数据：

3
2 1
3 1

输出数据：

1

解题思路

设置状态
dp[u][0]：表示u节点不被选择
dp[u][1]：表示u节点被选择
状态转移方程：
假设v1, v2…为u的子节点.

dp[u][0]

u节点不被选择，那么子节点一定被选择
dp[u][0] = dp[v1][1] + dp[v2][1] + …

dp[u][1]

u节点被选择，那么子节点可以被选择，也可以不被选择
dp[u][1] = min(dp[v1][0], dp[v1][1]) + min(dp[v2][0], dp[v2][1]) + …

总结转移方程如下

代码

from collections import defaultdict
# 节点数量
n = int(input())
# 树
edges = defaultdict(list)

def add(from_node, to_node):
    edges[from_node].append(to_node)

# 添加边
for _ in range(n-1):
    u, v = map(int, input().split())
    add(v, u)
    add(u, v)

# 不选 选的数量和
dp = [[0, 1] for i in range(0, n+1)]

def dfs(u, fa):
    for v in edges[u]:
        # 这里是无向树，要加上这一步判断，确保v是u的子节点
        if v == fa:
            continue
        dfs(v, u)
        dp[u][0] += dp[v][1]
        dp[u][1] += min(dp[v])

dfs(1, 0)
print(min(dp[1]))

最小支配集

问题特点

选择若干个点，使得树上的每一个点都被支配，即每一点要么自身被选择，要么相邻的节点被选择。
转化成图如下，橙色的节点表示被选中。

题目内容

找不到题目链接，输入数据的含义在代码里详细说明了。
输入数据：

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出数据：

25

解题思路

这里与前面两种类型不同，有三个状态，第三个状态表示：自身没被选，子节点也没被选择。如上图中的节点2就是这种情况。
设置状态
dp[u][0]：表示u节点被选择
dp[u][1]：表示u节点不被选择，子节点至少被选择了一个。
dp[u][2]：表示u节点不被选择，子节点没有一个被选。（这种状况只有在节点2的父节点1被选择才是合法，父节点1如果没被选择就是不合法的，也就是值为inf(无穷大)，会在计算过程中自动被淘汰，这个不用担心。）
状态转移方程：
假设v1, v2…为u的子节点.

dp[u][0]：

u节点被选择，那么子节点三种状态都可以选择。dp[u][2]是合法的哦。
dp[u][0] = min(dp[v1][0], dp[v1][1],dp[v1][2]) + min(dp[v2][0], dp[v2][1],dp[v2][2]) + …

dp[u][1]：

u节点不被选择，那么子节点至少被选择了一个。这里又是一个难点，如何让状态转移方程实现至少强迫选择一个。
推导过程如下：
假设没有要求至少选择一个，也就是说可以都不选，并且由于当前节点是没被选择的，所以对于子节点的第三种状态是不合法的，可以不写进去，当然想写也行，因为是inf，最小值怎么着也不会选到它。那么对应的公式就是：(min(dp[v1][0], dp[v1][1] + min(dp[v2][0], dp[v2][1]）+ …)
ok然后现在就是主要来避开一种情况，万一这一大坨公式(min(dp[v1][0], dp[v1][1] + min(dp[v2][0], dp[v2][1]）+ … )最小值的情况是都不选择，那就不满足了。所以我们至少要强迫选择一个子节点，并且让它对应的代价最小。对于每个节点，强迫选择的代价就是dp[v][0] - min(dp[v][0], dp[v][1])。现在来剖析一下这个式子，看看是不是能满足所有的情况。
假设这个节点在计算上面一大坨公式时，确实被选了，那么dp[v][0] - min(dp[v][0], dp[v][1]) = dp[v][0] - dp[v][0] = 0，那加入这一坨的代价为0，嗯对这一大坨公式没影响，也保证了至少有一个子节点被选择了的情况。
好的，那么假设这个节点在计算上面一大坨公式时，没被选，那么dp[v][0] - min(dp[v][0], dp[v][1]) = dp[v][0] - dp[v][1]，那再加上后面那一坨min(dp[v][0], dp[v][1]) = dp[v][1]，相互抵消，说明这个节点原本没选择的代价dp[v][1]刚好被选择的代价(dp[v][0]顶替了。那我们肯定要希望代价越小越好，所以总体转移方程要加上这一坨min((dp[v1][0] - min(dp[v1][0], dp[v1][1]) , (dp[v2][0] - min(dp[v2][0], dp[v2][1]), … )
所以dp[u][1] = (min(dp[v1][0], dp[v1][1] + min(dp[v2][0], dp[v2][1]）+ … ) + min((dp[v1][0] - min(dp[v1][0], dp[v1][1]) , (dp[v2][0] - min(dp[v2][0], dp[v2][1]), … )

dp[u][2]：

u节点不被选择，子节点没有一个被选，并且子节点的子节点一定至少被选一个，也就是对应dp[v][1]。
所以dp[u][2] = dp[v1][1] + dp[v2][1] + …

总结转移方程如下：

代码

from collections import defaultdict
# 总的节点数量
n = int(input())
# 为了找到根节点，找到rudu为0的节点
rudu = [-1] + [0]*n
# 点权
w = [0]*(n+1)
# 创建树
edges = defaultdict(list)
# 接下来的输入内容：节点的编号，节点的点权，节点的子节点数量，对应的子节点编号
# 遍历每个节点和处理对应的信息
for _ in range(n):
    shuru = list(map(int, input().split()))
    # 添加对应的权值
    w[shuru[0]] = shuru[1]
    # 遍历子节点
    if shuru[2] > 0:
        for i in range(3, 3 + shuru[2]):
            # 添加边
            edges[shuru[0]].append(shuru[i])
            # 入度减1
            rudu[shuru[i]] += 1
# print(rudu)
# print(w)
# print(edges)
# 父节点就是入度为0的节点
fa = rudu.index(0)
inf = 1e9
# 创建三个状态
dp = [[w[i], 0, 0] for i in range(n + 1)]

def dfs(u):
    min_daijia = inf
    for v in edges[u]:
        dfs(v)
        dp[u][0] += min(dp[v])
        dp[u][1] += min(dp[v][0], dp[v][1])
        # 计算最小代价，最后记得加上
        min_daijia = min(min_daijia, dp[v][0] - min(dp[v][0], dp[v][1]))
        dp[u][2] += dp[v][1]
    dp[u][1] += min_daijia

dfs(fa)
# dp[fa][2]不合法
print(min(dp[fa][0],dp[fa][1]))