目标
有一棵由 n 个节点组成的无向树，以 0 为根节点，节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges ，其中 edges[i] = [ai, bi] 表示在树上的节点 ai 和 bi 之间存在一条边。另给你一个下标从 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^5
- 0 <= coins[i] <= 10^4
- edges.length == n - 1
- 0 <=
edges[i][0], edges[i][1]< n - 0 <= k <= 10^4
提示：
- Let
dp[x][t]be the maximum points we can get from the subtree rooted at node x and the second operation has been used t times in its ancestors. - Note that the value of each node <= 104, so when t >= 14
dp[x][t]is always 0. - General equation will be:
dp[x][t] = max((coins[x] >> t) - k + sigma(dp[y][t]), (coins[x] >> (t + 1)) + sigma(dp[y][t + 1]))where nodes denoted by y in the sigma, are the direct children of node x.
思路
定义 dp[x][t] 表示 x 的祖先节点已经使用了 t 次方法二，当前节点及其子树所能获得的最大积分，最终结果为 dp[0][0]。状态转移方程为 dp[x][t] = Math.max(Σdp[c][t] + (coins[x] >> t) - k, Σdp[c][t + 1] + (coins[x] >> (t + 1)))，其中 c 是当前节点的直接孩子节点。
代码
/**
* @date 2025-01-23 10:20
*/
public class MaximumPoints2920 {
public int maximumPoints(int[][] edges, int[] coins, int k) {
int n = coins.length;
// 建图
List<Integer>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
g[from].add(to);
g[to].add(from);
}
// bfs 获得层级结构
List<List<Integer>> depthNodes = new ArrayList<>();
List<Integer> l = new ArrayList<>();
l.add(0);
depthNodes.add(l);
Queue<Integer> q = new ArrayDeque<>();
q.offer(0);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
Integer from = q.poll();
for (Integer to : g[from]) {
list.add(to);
g[to].removeIf(next -> next.equals(from));
}
}
if (list.size() > 0) {
depthNodes.add(list);
q.addAll(list);
}
}
// 初始化叶子节点的分数
int[][] dp = new int[n][15];
int depth = depthNodes.size();
for (Integer leaf : depthNodes.get(depth - 1)) {
for (int t = 0; t < 14; t++) {
dp[leaf][t] = Math.max((coins[leaf] >> t) - k, (coins[leaf] >> (t + 1)));
}
}
// 自底向上计算子树分数和的最大值
for (int d = depth - 2; d >= 0; d--) {
List<Integer> nodes = depthNodes.get(d);
for (Integer cur : nodes) {
for (int t = 0; t < 14; t++) {
int sum0 = 0;
int sum1 = 0;
for (Integer child : g[cur]) {
sum0 += dp[child][t];
sum1 += dp[child][t + 1];
}
dp[cur][t] = Math.max(sum0 + (coins[cur] >> t) - k, sum1 + (coins[cur] >> (t + 1)));
}
}
}
return dp[0][0];
}
}
性能
