树的最大权独立集：树形DP

摘要: 树形DP解决树上最大权独立集问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

对于没有自环的图 $D$，$S$ 为 $V(D)$ 的子集，若 $S$ 中任意两点均不相邻，则称 $S$ 为 D 的独立集。

如果图中每个点 $u$ 有一个权值 $f[u]$，则使得独立集中各点的权值和 $\sum\limits_{u\in V}f[u]$ 最大的独立集称为最大权独立集。

图上的最大权独立集问题是 NP-Hard 问题，但如果是树上，可以用树形 DP 解决。本文我们以 2646. 最小化旅行的价格总和 为例看一下具体是怎么做的。

此外本题在预处理阶段的过程刚好是树上差分解决的问题，此前我们了解过该算法并给出了代码模板，参考文章 树上差分，这里可以直接套用代码模板。

---

题目

2646. 最小化旅行的价格总和

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

提示：

1 <= n <= 50
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1

示例 1：

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

题解

算法：树形DP

设该树为 $G$，每个点都有一个权值，记为 $p[u]$，表示 $u$ 点的费用。

首先考察查询 trips[i] = si, ti，表示要从 si 走到 ti。由于是树，因此路径唯一，在这条路径上会经过一系列点，每经过一个点 $u$，都要付出费用 $p[u]$。

将 trips 中的若干次查询都考察完之后，对每个点记录一个经过的次数 $cnt[u]$，表示在 trips 中经过 $u$ 点的次数。这样总的费用为：

$$T = \sum\limits_{u\in V}cnt[u]p[u]$$

现在可以从 $G$ 中选出一组独立集 $S \subset V$，独立集上的总费用为：

$$T_{1} = \sum\limits_{u\in S}cnt[u]p[u]$$

独立集上的费用可以减半，因此可以减掉的费用为 $T_{1} / 2$。因此我们希望 $T_{1}$ 尽可能大。

如果记 $f[u] = cnt[u]p[u]$ 为点 $u$ 的权，我们要做的是在树 $G$ 上找到最大权独立集 $S$，其最大权为 $T_{1}$，这样最终的总费用为 $T - T_{1}/2$。

下面用树形 DP 解决树的最大权独立集问题。

状态定义 $dp[u][s]$ 表示在子树 $u$ 上的最大权独立集，$s$ 为附加信息，取值为 0，1。$s = 0$ 表示子树的根 $u$ 不在选出的独立集中，$s = 1$ 表示子树的根 $u$ 在选出的独立集中。

这样定义的话，目标为 $\max(dp[root][0], dp[root][1])$，边界值为 $dp[leaf][0] = 0, dp[leaf][1] = f[leaf]$。

下面考察状态转移方程，对 $u$ 点来说，其子节点为 $v_{i}, i=0,1,\cdots$。如果 $u$ 选入独立集，那么 $v_{i}$ 就不能选，如果 $u$ 不选入独立集，那么 $v_{i}$ 可选可不选。于是状态转移方程如下：

$$dp[u][0] = \sum\limits_{v \in son(u)}\max(dp[v][0], dp[v][1])$$ $$dp[u][1] = f[u] + \sum\limits_{v \in son(u)}dp[v][0]$$

代码 (Python)

记 trips 的起点终点共 $m$ 对，树的节点数为 $n$。算法分为两部分，第一部分是考察 trips 中的每一对起点终点，获取起点到终点路径上的每个点，然后将次数 +1；时间复杂度为 $O(mn)$，第二部分为树形 DP 的部分，这部分的时间复杂度为 $O(n)$，因此总时间复杂度为 $O(mn)$。

如果 $m$ 很大的话，就需要优化预处理的过程。

def ignore_args(*args_to_ignore):
    def decorator(func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            new_args = [arg for arg in args if arg not in args_to_ignore]
            return func(*new_args, **kwargs)
        return wrapper
    return decorator

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        self.g = [[] for _ in range(n)]
        for u, v in edges:
            self.g[u].append(v)
            self.g[v].append(u)

        ans = 0
        cnt = [0 for _ in range(n)]
        for s, t in trips:
            path = []
            self.get_path(s, -1, t, path)
            for u in path:
                cnt[u] += 1
                ans += price[u]

        self.f = [0 for _ in range(n)]
        for i in range(n):
            self.f[i] = cnt[i] * price[i]

        T1 = self.solve(0, 0, -1)
        T2 = self.solve(0, 1, -1)
        print("T1: {}".format(T1))
        print("T2: {}".format(T2))
        T = max(T1, T2)
        ans -= int(T / 2)

        return ans

    @ignore_args("fa")
    @lru_cache(int(1e7))
    def solve(self, u, s, fa):
        if len(self.g[u]) == 1 and fa != -1:
            return self.f[u] if s == 1 else 0

        ans = 0
        for v in self.g[u]:
            if v == fa:
                continue
            if s == 0:
                ans += max(self.solve(v, 0, u), self.solve(v, 1, u))
            else:
                ans += self.solve(v, 0, u)
        if s == 1:
            ans += self.f[u]

        return ans

    def get_path(self, u, fa, t, path):
        path.append(u)
        if u == t:
            return True
        for v in self.g[u]:
            if v == fa:
                continue
            if self.get_path(v, u, t, path):
                return True
        path.pop()
        return False

优化：树上差分

树上差分解决的是以下问题：

给定一棵树，共 N 个节点，编号为 0 ~ N - 1，初始时点的权均为 0。
执行若干次操作，每次操作给定两个节点 x、y，将 xy 路径上所有节点的权加 1。
询问某个节点 x 的权。

而本的预处理过程是：考察 trips 中的查询 (u, v)，对 u 到 v 的路径上的每个点，将其次数 +1。最终我们要的是每个顶点的经过次数 cnt[u]。

这个处理过程与树上差分解决的问题吻合，因此可以用树上差分来做。算法和代码模板参考文章 树上差分。

代码 (Python，模板)

树上差分的部分完全套用 树上差分 中的代码模板，将 C++ 改为了 Python。

def get_parent(g: List[List[int]], u: int, prev: int, d: List[int], parent: List[int]) -> None:
    for v in g[u]:
        if v == prev:
            continue
        d[v] = d[u] + 1
        parent[v] = u
        get_parent(g, v, u, d, parent)

def get_fa(parent: List[int], fa: List[List[int]], N: int, M: int) -> None:
    # fa[i][j] := 从 i 爬 2 ^ j 步所到点的 id
    # fa[i][0] := 从 i 爬 1 不所到点的 id
    for i in range(1, N + 1):
        fa[i][0] = parent[i]
    for j in range(1, M):
        fa[0][j] = -1
    for j in range(1, M):
        for i in range(1, N + 1):
            if fa[i][j - 1] == -1:
                fa[i][j] = -1
            else:
                fa[i][j] = fa[fa[i][j - 1]][j - 1]

# ----- LCA -----

def lowbit(n: int) -> int:
    return n & (-n);

def highbit(n: int) -> int:
    p = lowbit(n);
    while p != n:
        n -= p;
        p = lowbit(n);
    return p;

def lca(x: int, y: int, d: List[int], fa: List[List[int]]) -> int:
    # d[x] >= d[y]
    if d[x] < d[y]:
        return lca(y, x, d, fa)
    # 将 y 向上调整直到和 x 一个深度
    delta = d[x] - d[y]
    while delta > 0:
        x = fa[x][int(log2(highbit(delta)))]
        delta -= highbit(delta)
    if x == y:
        return x;
    M = len(fa[0])
    while True:
        if fa[x][0] == fa[y][0]:
            break
        k = 0
        while k <= M:
            if fa[x][k] == -1 or fa[y][k] == -1:
                break
            if fa[x][k] == fa[y][k]:
                break
            k += 1
        x = fa[x][k - 1]
        y = fa[y][k - 1]
    return fa[x][0]

# --- 树上差分 ---

def dfs(g: List[List[int]], u: int, prev: int, diff: List[int], sums: List[int]) -> None:
    for v in g[u]:
        if v == prev:
            continue
        dfs(g, v, u, diff, sums)
        sums[u] += sums[v]
    sums[u] += diff[u]

在以上树上差分的代码模板中，图的编号是 1 ~ N，为了直接调用模板而不改变模板内部代码，在以下题解代码中把 0 ~ N - 1 转换为了 1 ~ N。

def ignore_args(*args_to_ignore):
    def decorator(func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            new_args = [arg for arg in args if arg not in args_to_ignore]
            return func(*new_args, **kwargs)
        return wrapper
    return decorator

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        self.g = [[] for _ in range(n + 1)]
        for u, v in edges:
            self.g[u + 1].append(v + 1)
            self.g[v + 1].append(u + 1)

        # 树上差分
        d = [0 for _ in range(n + 1)]
        M = int(log2(n)) + 1
        parent = [0 for _ in range(n + 1)]
        get_parent(self.g, 1, -1, d, parent) # 视 1 为根

        fa = [[0 for _ in range(M)] for _ in range(n + 1)]
        get_fa(parent, fa, n, M)

        diff = [0 for _ in range(n + 1)]
        for s, t in trips:
            s += 1
            t += 1
            diff[s] += 1
            diff[t] += 1
            diff[lca(s, t, d, fa)] -= 1
            diff[parent[lca(s, t, d, fa)]] -= 1

        cnt = [0 for _ in range(n + 1)]
        dfs(self.g, 1, -1, diff, cnt)

        print(cnt)

        # 树形 DP
        ans = 0
        self.f = [0 for _ in range(n + 1)]
        for i in range(1, n + 1):
            self.f[i] = cnt[i] * price[i - 1]
            ans += self.f[i]

        T1 = self.solve(1, 0, -1)
        T2 = self.solve(1, 1, -1)
        print("T1: {}".format(T1))
        print("T2: {}".format(T2))
        T = max(T1, T2)
        ans -= int(T / 2)

        return ans

    @ignore_args("fa")
    @lru_cache(int(1e7))
    def solve(self, u, s, fa):
        if len(self.g[u]) == 1 and fa != -1:
            return self.f[u] if s == 1 else 0

        ans = 0
        for v in self.g[u]:
            if v == fa:
                continue
            if s == 0:
                ans += max(self.solve(v, 0, u), self.solve(v, 1, u))
            else:
                ans += self.solve(v, 0, u)
        if s == 1:
            ans += self.f[u]

        return ans

---