# 2920. Maximum Points After Collecting Coins From All Nodes

## Description

There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given a 0-indexed array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.

Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.

Coins at nodei can be collected in one of the following ways:

• Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
• Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).

Return the maximum points you can get after collecting the coins from all the tree nodes.

Example 1:

Input: edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
Output: 11
Explanation:
Collect all the coins from node 0 using the first way. Total points = 10 - 5 = 5.
Collect all the coins from node 1 using the first way. Total points = 5 + (10 - 5) = 10.
Collect all the coins from node 2 using the second way so coins left at node 3 will be floor(3 / 2) = 1. Total points = 10 + floor(3 / 2) = 11.
Collect all the coins from node 3 using the second way. Total points = 11 + floor(1 / 2) = 11.
It can be shown that the maximum points we can get after collecting coins from all the nodes is 11.


Example 2:

Input: edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
Output: 16
Explanation:
Coins will be collected from all the nodes using the first way. Therefore, total points = (8 - 0) + (4 - 0) + (4 - 0) = 16.


Constraints:

• n == coins.length
• 2 <= n <= 105
• 0 <= coins[i] <= 104
• edges.length == n - 1
• 0 <= edges[i][0], edges[i][1] < n
• 0 <= k <= 104

## Solutions

• class Solution {
private int k;
private int[] coins;
private Integer[][] f;
private List<Integer>[] g;

public int maximumPoints(int[][] edges, int[] coins, int k) {
this.k = k;
this.coins = coins;
int n = coins.length;
f = new Integer[n][15];
g = new List[n];
Arrays.setAll(g, i -> new ArrayList<>());
for (var e : edges) {
int a = e[0], b = e[1];
}
return dfs(0, -1, 0);
}

private int dfs(int i, int fa, int j) {
if (f[i][j] != null) {
return f[i][j];
}
int a = (coins[i] >> j) - k;
int b = coins[i] >> (j + 1);
for (int c : g[i]) {
if (c != fa) {
a += dfs(c, i, j);
if (j < 14) {
b += dfs(c, i, j + 1);
}
}
}
return f[i][j] = Math.max(a, b);
}
}

• class Solution {
public:
int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
int n = coins.size();
int f[n][15];
memset(f, -1, sizeof(f));
vector<int> g[n];
for (auto& e : edges) {
int a = e[0], b = e[1];
g[a].emplace_back(b);
g[b].emplace_back(a);
}
function<int(int, int, int)> dfs = [&](int i, int fa, int j) {
if (f[i][j] != -1) {
return f[i][j];
}
int a = (coins[i] >> j) - k;
int b = coins[i] >> (j + 1);
for (int c : g[i]) {
if (c != fa) {
a += dfs(c, i, j);
if (j < 14) {
b += dfs(c, i, j + 1);
}
}
}
return f[i][j] = max(a, b);
};
return dfs(0, -1, 0);
}
};

• 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


• func maximumPoints(edges [][]int, coins []int, k int) int {
n := len(coins)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, 15)
for j := range f[i] {
f[i][j] = -1
}
}
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
var dfs func(int, int, int) int
dfs = func(i, fa, j int) int {
if f[i][j] != -1 {
return f[i][j]
}
a := (coins[i] >> j) - k
b := coins[i] >> (j + 1)
for _, c := range g[i] {
if c != fa {
a += dfs(c, i, j)
if j < 14 {
b += dfs(c, i, j+1)
}
}
}
f[i][j] = max(a, b)
return f[i][j]
}
return dfs(0, -1, 0)
}

• function maximumPoints(edges: number[][], coins: number[], k: number): number {
const n = coins.length;
const f: number[][] = Array.from({ length: n }, () => Array(15).fill(-1));
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
const dfs = (i: number, fa: number, j: number): number => {
if (f[i][j] !== -1) {
return f[i][j];
}
let a = (coins[i] >> j) - k;
let b = coins[i] >> (j + 1);
for (const c of g[i]) {
if (c !== fa) {
a += dfs(c, i, j);
if (j < 14) {
b += dfs(c, i, j + 1);
}
}
}
return (f[i][j] = Math.max(a, b));
};
return dfs(0, -1, 0);
}