Hard

题目描述

存在一个以节点 0 为根的 n 个节点的无向树，节点标记为 0 到 n - 1。给定一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。还给定一个大小为 n 的 0 索引数组 coins，其中 coins[i] 表示顶点 i 中的硬币数量，以及一个整数 k。

从根节点开始，你必须收集所有硬币，使得只有在已经收集了节点祖先的硬币后，才能收集该节点的硬币。

节点 i 的硬币可以通过以下方式之一收集：

  1. 收集所有硬币，但你将获得 coins[i] - k 分。如果 coins[i] - k 为负数，则你将失去 abs(coins[i] - k) 分。
  2. 收集所有硬币，但你将获得 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^5
  • 0 <= coins[i] <= 10^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= k <= 10^4

解题思路

这是一个经典的树形动态规划问题。关键在于理解两种收集方式的影响：

核心思路：

  1. 状态定义：设 dp[x][t] 表示从节点 x 的子树中能获得的最大分数，其中 t 表示该节点的祖先中使用第二种方式（除以2）的次数。

  2. 状态转移：对于每个节点，我们有两种选择：

    • 使用第一种方式：获得 (coins[x] >> t) - k 分，子节点的除以2次数保持为 t
    • 使用第二种方式：获得 (coins[x] >> (t+1)) 分，子节点的除以2次数变为 t+1

  3. 剪枝优化：当 t >= 14 时，由于 coins[i] <= 10^4，此时 coins[i] >> 14 必定为 0，可以直接返回 0。

  4. 记忆化搜索：使用记忆化避免重复计算，提高效率。

状态转移方程：

dp[x][t] = max(
    (coins[x] >> t) - k + sum(dp[child][t]),
    (coins[x] >> (t+1)) + sum(dp[child][t+1])
)

代码实现

class Solution {
public:
    int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
        int n = coins.size();
        vector<vector<int>> graph(n);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<int> parent(n, -2);
        vector<int> order = {0};
        parent[0] = -1;
        for (int index = 0; index < n; index++) {
            int node = order[index];
            for (int child : graph[node]) {
                if (child == parent[node]) continue;
                parent[child] = node;
                order.push_back(child);
            }
        }

        vector<vector<int>> dp(n, vector<int>(15));
        for (int index = n - 1; index >= 0; index--) {
            int node = order[index];
            for (int shifts = 13; shifts >= 0; shifts--) {
                int keep = (coins[node] >> shifts) - k;
                int halve = coins[node] >> (shifts + 1);

                for (int child : graph[node]) {
                    if (parent[child] != node) continue;
                    keep += dp[child][shifts];
                    halve += dp[child][shifts + 1];
                }
                dp[node][shifts] = max(keep, halve);
            }
        }

        return dp[0][0];
    }
};

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        n = len(coins)
        graph = [[] for _ in range(n)]

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        parent = [-2] * n
        parent[0] = -1
        order = [0]
        for node in order:
            for child in graph[node]:
                if child == parent[node]:
                    continue
                parent[child] = node
                order.append(child)

        dp = [[0] * 15 for _ in range(n)]
        for node in reversed(order):
            for shifts in range(13, -1, -1):
                keep = (coins[node] >> shifts) - k
                halve = coins[node] >> (shifts + 1)

                for child in graph[node]:
                    if parent[child] != node:
                        continue
                    keep += dp[child][shifts]
                    halve += dp[child][shifts + 1]
                dp[node][shifts] = max(keep, halve)

        return dp[0][0]

public class Solution {
    public int MaximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.Length;
        var graph = new List<List<int>>();
        for (int i = 0; i < n; i++) {
            graph.Add(new List<int>());
        }

        foreach (int[] edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = -2;
        parent[0] = -1;
        var order = new List<int> {0};
        for (int index = 0; index < n; index++) {
            int node = order[index];
            foreach (int child in graph[node]) {
                if (child == parent[node]) continue;
                parent[child] = node;
                order.Add(child);
            }
        }

        int[][] dp = new int[n][];
        for (int i = 0; i < n; i++) dp[i] = new int[15];

        for (int index = n - 1; index >= 0; index--) {
            int node = order[index];
            for (int shifts = 13; shifts >= 0; shifts--) {
                int keep = (coins[node] >> shifts) - k;
                int halve = coins[node] >> (shifts + 1);

                foreach (int child in graph[node]) {
                    if (parent[child] != node) continue;
                    keep += dp[child][shifts];
                    halve += dp[child][shifts + 1];
                }
                dp[node][shifts] = Math.Max(keep, halve);
            }
        }

        return dp[0][0];
    }
}

var maximumPoints = function(edges, coins, k) {
    const n = coins.length;
    const graph = Array.from({length: n}, () => []);

    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }

    const parent = new Int32Array(n);
    parent.fill(-2);
    parent[0] = -1;
    const order = [0];
    for (let index = 0; index < order.length; index++) {
        const node = order[index];
        for (const child of graph[node]) {
            if (child === parent[node]) continue;
            parent[child] = node;
            order.push(child);
        }
    }

    const dp = Array.from({length: n}, () => new Int32Array(15));
    for (let index = n - 1; index >= 0; index--) {
        const node = order[index];
        for (let shifts = 13; shifts >= 0; shifts--) {
            let keep = (coins[node] >> shifts) - k;
            let halve = coins[node] >> (shifts + 1);

            for (const child of graph[node]) {
                if (parent[child] !== node) continue;
                keep += dp[child][shifts];
                halve += dp[child][shifts + 1];
            }
            dp[node][shifts] = Math.max(keep, halve);
        }
    }

    return dp[0][0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × log(max(coins)))
空间复杂度O(n × log(max(coins)))

说明：

  • 时间复杂度：每个节点最多被访问 14 次（因为 log₂(10⁴) ≈ 14），所以总时间复杂度为 O(n × 14) = O(n)
  • 空间复杂度：邻接表、显式遍历顺序和 DP 数组均为 O(n)，不再依赖递归栈