【Leetcode 每日一题】2920. 收集所有金币可获得的最大积分

问题背景

有一棵由 $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)$。
  返回收集 所有 树节点的金币之后可以获得的最大积分。

数据约束

• $n=coins.length$
• $2\le n\le 10^5$
• $0\le coins[i]\le 10^4$
• $edges.length=n-1$
• $0\le edges[i][0],edges[i][1]<n$
• $0\le k\le 10^4$

解题过程

这题比较麻烦的地方在于不好记录除法到底进行了多少次，看了 灵神的题解，才意识到把除法转化成右移，还可以避免边界的处理。
状态转移方程是现成的，也可以比较方便地翻译成递推。

处理树的过程中还需要额外注意一点，递归的时候只能枚举子节点，不能往父节点走，为此需要在方法中多定义一个参数。

具体实现

递归

class Solution {public int maximumPoints(int[][] edges, int[] coins, int k) {int n = coins.length;// 树和图是类似的，用图的手段建立一般树List<Integer>[] graph = new ArrayList[n];Arrays.setAll(graph, i -> new ArrayList<>());for (int[] edge : edges) {int x = edge[0];int y = edge[1];graph[x].add(y);graph[y].add(x);}int[][] memo = new int[n][14];// 在每个节点处，零是可能的结果，数组元素要初始化为 -1for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(0, 0, -1, memo, graph, coins, k);}private int dfs (int i, int j, int father, int[][] memo, List<Integer>[] graph, int[] coins, int k) {if (memo[i][j] != -1) {return memo[i][j];}int res1 = (coins[i] >> j) - k;int res2 = coins[i] >> (j + 1);// 遍历所有子节点for (int child : graph[i]) {// 如果当前枚举到的节点是父节点，那跳过当前轮次if (child == father) {continue;}res1 += dfs(child, j, i, memo, graph, coins, k);// 如果还能右移，那进一步计算右移的情形if (j < 13) {res2 += dfs(child, j + 1, i, memo, graph, coins, k);}}// 记录结果并返回return memo[i][j] = Math.max(res1, res2);}
}

递推

class Solution {public int maximumPoints(int[][] edges, int[] coins, int k) {// 树和图是类似的，用图的手段建立一般树List<Integer>[] graph = new ArrayList[coins.length];Arrays.setAll(graph, i -> new ArrayList());for (int[] edge : edges) {int x = edge[0];int y = edge[1];graph[x].add(y);graph[y].add(x);}return dfs(0, -1, graph, coins, k)[0];}private int[] dfs(int x, int father, List<Integer>[] graph, int[] coins, int k) {int[] dp = new int[14];for (int y : graph[x]) {if(y == father) {continue;}// 自底向上，先确定子节点的值int[] res = dfs(y, x, graph, coins, k);for (int j = 0; j < 14; j++) {dp[j] += res[j];}}for (int j = 0; j < 13; j++) {dp[j] = Math.max((coins[x] >> j) - k + dp[j], (coins[x] >> (j + 1)) + dp[j + 1]);}// 如果继续右移结果一定为零，这种情况要单独赋值dp[13] += (coins[x] >> 13) - k;return dp;}
}