What is the core pattern in the Maximum Points After Collecting Coins From All Nodes problem?

The core pattern involves binary-tree traversal combined with dynamic programming and state tracking to maximize the total points from coin collection.

How can dynamic programming be applied to this problem?

Dynamic programming is used to store intermediate results for subproblems, allowing the efficient calculation of maximum points from each subtree while tracking the state transitions.

What are the key challenges in solving Maximum Points After Collecting Coins From All Nodes?

Key challenges include handling both coin collection methods efficiently and using memoization to avoid redundant calculations.

What does the second coin collection method do in this problem?

The second method allows for half of the coins to be collected, reducing the total but leaving coins in the node that are halved for further collection.

How does GhostInterview assist in solving this problem?

GhostInterview breaks down the problem into digestible steps, providing insights on dynamic programming, state tracking, and efficient tree traversal.

#2920

Hard

auto_awesome二分·树·traversal

LeetCode 题解工作台

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

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

数组动态规划位运算树深度优先搜索

题目描述

有一棵由 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⁴

lightbulb

解题思路

方法一：记忆化搜索

我们先根据题目给定的边构建图 $g$ ，其中 $g[i]$ 表示节点 $i$ 的所有邻接节点。然后我们可以使用记忆化搜索的方法求解本题。

我们设计一个函数 $dfs(i, fa, j)$ ，表示当前节点为 $i$ ，父节点为 $fa$ ，当前节点的金币数需要右移 $j$ 位，所能获得的最大积分。

函数 $dfs(i, fa, j)$ 的执行过程如下：

如果我们使用第一种方法收集当前节点的金币，那么当前节点的积分为 $(coins[i] >> j) - k$ ，然后我们遍历当前节点的所有邻接节点 $c$ ，如果 $c$ 不等于 $fa$ ，那么我们将 $dfs(c, i, j)$ 的结果累加到当前节点的积分中。

如果我们使用第二种方法收集当前节点的金币，那么当前节点的积分为 $coins[i] >> (j + 1)$ ，然后我们遍历当前节点的所有邻接节点 $c$ ，如果 $c$ 不等于 $fa$ ，那么我们将 $dfs(c, i, j + 1)$ 的结果累加到当前节点的积分中。注意，由于题目中给定的 $coins[i]$ 最大值为 $10^4$ ，因此我们最多只能右移 $14$ 位，就使得 $coins[i] >> (j + 1)$ 的值为 $0$ 。

最后，我们返回当前节点使用两种方法中能获得的最大积分。

为了避免重复计算，我们使用记忆化搜索的方法，将 $dfs(i, fa, j)$ 的结果存储到 $f[i][j]$ 中，其中 $f[i][j]$ 表示当前节点为 $i$ ，父节点为 $fa$ ，当前节点的金币数需要右移 $j$ 位，所能获得的最大时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(n \times \log M)$ 。其中 $M$ 表示 $coins[i]$ 的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        @cache
        def dfs(i: int, fa: int, j: int) -> int:
            a = (coins[i] >> j) - k
            b = coins[i] >> (j + 1)
            for c in g[i]:
                if c != fa:
                    a += dfs(c, i, j)
                    if j < 14:
                        b += dfs(c, i, j + 1)
            return max(a, b)

        n = len(coins)
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        ans = dfs(0, -1, 0)
        dfs.cache_clear()
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate efficiently use dynamic programming and memoization to avoid redundant calculations?
question_mark
Can the candidate demonstrate understanding of how state tracking helps maximize the points for this problem?
question_mark
Does the candidate effectively use depth-first search for tree traversal while considering the two coin collection methods?

warning

常见陷阱

外企场景

error
Failing to implement the second coin collection method properly and not adjusting the remaining coins correctly.
error
Not using memoization or dynamic programming to store intermediate results, leading to inefficient solutions.
error
Incorrectly handling the state transitions, especially when switching between the two coin collection methods.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variation 1: What if coins are collected in a specific order or with additional constraints?
arrow_right_alt
Variation 2: How does the problem change if the tree is not binary, or if nodes can have more than two children?
arrow_right_alt
Variation 3: What if you had to collect coins starting from multiple nodes simultaneously?

help

常见问题

外企场景

继续练习

#3575 最大好子树分数 #2791 树中可以形成回文的路径数 #3068 最大节点价值之和