题目描述
节点 0
处现有一棵由 n
个节点组成的无向树,节点编号从 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)
。
返回收集 所有 树节点的金币之后可以获得的最大积分。
样例
输入: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。
输入: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
算法
(动态规划) $O(n \log coin)$
- 注意到,由于 $coin$ 有上限,所以在收集过程中,如果执行超过 $14$ 次第二种方法,则后续所有金币的收集都可以视为 $0$。
- 设状态 $f(i, j)$ 表示以节点 $i$ 为根的子树,从根节点到 $i$ 时共执行了 $j$ 次第二种方法时的最大总积分。
- 从节点 $0$ 开始递归,统计执行了 $j$ 次第二种方法时,以 $i$ 为根的所有子节点的积分总和 $t(j)$。
- 对于节点 $i$,枚举 $j$,如果当前节点执行第一种方法,则可以转移 $t(j) + x / 2^j - k$,如果执行第二种方法,则转移 $t(j + 1) + x / 2^{j + 1}$;二者取最大值。
- 最终答案为 $\max(f(0, j))$。
时间复杂度
- 状态数为 $O(n \log coin)$,转移时间为常数,故总时间复杂度为 $o(n \log coin)$。
空间复杂度
- 需要 $O(n \log coin)$ 的额外空间存储邻接表,动态规划的状态和递归的系统栈。
C++ 代码
const int N = 100010, M = 15;
class Solution {
private:
vector<vector<int>> graph;
int f[N][M];
void solve(int u, int fa, const vector<int> &coins, int k) {
int t[M + 1];
memset(t, 0, sizeof(t));
for (int v : graph[u]) {
if (v == fa)
continue;
solve(v, u, coins, k);
for (int j = 0; j < M; j++) {
t[j] += f[v][j];
}
}
int x = coins[u];
for (int j = 0; j < M; j++) {
f[u][j] = max(t[j] + x - k, t[j + 1] + x / 2);
x /= 2;
}
}
public:
int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
const int n = coins.size();
graph.resize(n);
for (const auto &e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
solve(0, -1, coins, k);
int ans = 0;
for (int j = 0; j < M; j++)
ans = max(ans, f[0][j]);
return ans;
}
};