收集所有金币可获得的最大积分

难度: Hard

有一棵由 n 个节点组成的无向树，以 0 为根节点，节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a_i, b_i] 表示在树上的节点 a_i 和 b_i 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ，其中 coins[i] 表示节点 i 处的金币数量。

从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。

节点 i 上的金币可以用下述方法之一进行收集：

收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。
收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。

返回收集所有树节点的金币之后可以获得的最大积分。

示例 1：

输入：edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
输出：11                        
解释：
使用第一种方法收集节点 0 上的所有金币。总积分 = 10 - 5 = 5 。
使用第一种方法收集节点 1 上的所有金币。总积分 = 5 + (10 - 5) = 10 。
使用第二种方法收集节点 2 上的所有金币。所以节点 3 上的金币将会变为 floor(3 / 2) = 1 ，总积分 = 10 + floor(3 / 2) = 11 。
使用第二种方法收集节点 3 上的所有金币。总积分 =  11 + floor(1 / 2) = 11.
可以证明收集所有节点上的金币能获得的最大积分是 11 。

示例 2：

输入：edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
输出：16
解释：
使用第一种方法收集所有节点上的金币，因此，总积分 = (8 - 0) + (4 - 0) + (4 - 0) = 16 。

提示：

n == coins.length
2 <= n <= 10⁵
0 <= coins[i] <= 10⁴
edges.length == n - 1
0 <= edges[i][0], edges[i][1] < n
0 <= k <= 10⁴

Submission

运行时间: 613 ms

内存: 64.3 MB

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        g = [[] for _ in range(len(coins))]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        

        @cache
        def dfs(x, fa, half):
            v1 = (coins[x] >> half) - k
            v2 = coins[x] >> (half + 1)
            for y in g[x]:
                if y != fa:
                    v1 += dfs(y, x, half)
                    if half < 13:
                        v2 += dfs(y, x, half + 1)
            return max(v1, v2)
        return dfs(0, -1, 0)

Explain

这个题解采用了深度优先搜索（DFS）结合记忆化的方式来解决问题。首先，构建了一个邻接表g来表示树的结构。然后，定义了一个递归函数dfs，用于从某个节点x开始，尝试以两种不同的策略收集金币，并返回可能的最大金币数量。这两种策略分别是：1) 当前节点的金币数右移half位然后减去k；2) 当前节点的金币数右移half+1位。对于每个节点，递归地调用其子节点的dfs函数，并将结果累加到当前节点的策略中。最后，对于每个节点，取两种策略中的最大值。递归的终止条件是当half超过13时，不再递归调用half+1的情况。整个过程从根节点开始，递归遍历整棵树，最终返回根节点可以获得的最大金币数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        g = [[] for _ in range(len(coins))]  # 创建邻接表
        for x, y in edges:
            g[x].append(y)  # 无向边，添加两次
            g[y].append(x)
        
        @cache  # 使用缓存避免重复计算
        def dfs(x, fa, half):
            v1 = (coins[x] >> half) - k  # 策略1：右移half位后减k
            v2 = coins[x] >> (half + 1)  # 策略2：右移half+1位
            for y in g[x]:
                if y != fa:  # 避免向父节点递归
                    v1 += dfs(y, x, half)  # 累加子节点的最大值
                    if half < 13:
                        v2 += dfs(y, x, half + 1)  # 如果half < 13，考虑下一个half值
            return max(v1, v2)  # 选择两种策略的较大值
        return dfs(0, -1, 0)  # 从根节点开始递归

Explore

在DFS的实现中，通过传递一个父节点参数`fa`来避免循环调用。当递归访问子节点时，检查子节点是否为当前节点的父节点，如果不是，则进行递归调用。这样可以确保不会向父节点递归，从而避免循环。此外，使用`@cache`装饰器来缓存已计算的结果，防止对同一状态的重复计算。这种记忆化方法显著提高了算法的效率，避免了重复的工作。

题解中的两种策略通过不同的位移操作来模拟可能的金币收集策略，提供灵活的选择以最大化金币收集。策略1通过右移`half`位然后减去固定值`k`来模拟一种收集成本或损耗，可能代表在收集过程中的某种损耗或代价。策略2通过进一步右移一位来代表在不同条件下的另一种可能性或保守估计。这两种策略允许算法在不同层级递归中权衡并选择最优解，而位移操作本身是一种高效的计算方式，适合快速处理大量数据。

参数`half`在递归函数`dfs`中用于控制金币的位移操作。随着`half`的增加，金币数会被进一步右移，这意味着在递归深入的过程中采取更加保守的金币计算策略。`half`的变化允许函数在不同深度的递归中尝试不同程度的位移，从而探索收集金币的不同策略。这是一种灵活调整策略，以适应可能的最大收益。递归的终止条件是`half`超过13时，不再递归调用`half+1`的情况，这避免了过度的位移导致的无效运算。