[LC] 2920 Maximum Points After Collecting Coins From All Nodes

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/maximum-points-after-collecting-coins-from-all-nodes/">Maximum Points after Collecting Coins from All Nodes</a>
 * 位运算；树；深度优先搜索；数组；动态规划
 */
class Solution {
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            children.get(edge[0]).add(edge[1]);
            children.get(edge[1]).add(edge[0]);
        }
        int[][] memo = new int[n][14];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(0, -1, 0, coins, k, children, memo);
    }

    private int dfs(int node, int parent, int f, int[] coins, int k, List<List<Integer>> children, int[][] memo) {
        if (memo[node][f] != -1) {
            return memo[node][f];
        }
        int res0 = (coins[node] >> f) - k;
        int res1 = coins[node] >> (f + 1);
        for (int child : children.get(node)) {
            if (child == parent) {
                continue;
            }
            res0 += dfs(child, node, f, coins, k, children, memo);
            if (f + 1 < 14) {
                res1 += dfs(child, node, f + 1, coins, k, children, memo);
            }
        }
        memo[node][f] = Math.max(res0, res1);
        return memo[node][f];
    }
}

Go

func maximumPoints(edges [][]int, coins []int, k int) int {
    n := len(coins)
    children := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        children[u] = append(children[u], v)
        children[v] = append(children[v], u)
    }

    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, 14)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var dfs func(node, parent, f int) int
    dfs = func(node, parent, f int) int {
        if memo[node][f] >= 0 {
            return memo[node][f]
        }
        res0, res1 := (coins[node]>>f)-k, coins[node]>>(f+1)
        for _, child := range children[node] {
            if child == parent {
                continue
            }
            res0 += dfs(child, node, f)
            if f+1 < 14 {
                res1 += dfs(child, node, f+1)
            }
        }
        memo[node][f] = int(max(float64(res0), float64(res1)))
        return memo[node][f]
    }

    return dfs(0, -1, 0)
}

JavaScript

var maximumPoints = function (edges, coins, k) {
    const n = coins.length;
    const children = Array.from({length: n}, () => []);
    for (const edge of edges) {
        children[edge[0]].push(edge[1]);
        children[edge[1]].push(edge[0]);
    }
    const memo = Array.from({length: n}, () => Array(14).fill(-1));

    const dfs = (node, parent, f) => {
        if (memo[node][f] >= 0) {
            return memo[node][f];
        }
        let res0 = (coins[node] >> f) - k, res1 = coins[node] >> (f + 1);
        for (const child of children[node]) {
            if (child === parent) {
                continue;
            }
            res0 += dfs(child, node, f);
            if (f + 1 < 14) {
                res1 += dfs(child, node, f + 1);
            }
        }
        return memo[node][f] = Math.max(res0, res1);
    };

    return dfs(0, -1, 0);
};

PHP

class Solution {
    /**
     * @param Integer[][] $edges
     * @param Integer[] $coins
     * @param Integer $k
     * @return Integer
     */
    function maximumPoints(array $edges, array $coins, int $k): int {
        $n = count($coins);
        $children = array_fill(0, $n, []);
        foreach ($edges as $edge) {
            $children[$edge[0]][] = $edge[1];
            $children[$edge[1]][] = $edge[0];
        }
        $memo = array_fill(0, $n, array_fill(0, 14, -1));
        return $this->dfs(0, -1, 0, $coins, $k, $children, $memo);
    }

    function dfs($node, $parent, $f, $coins, $k, $children, &$memo) {
        if ($memo[$node][$f] != -1) {
            return $memo[$node][$f];
        }
        $res0 = ($coins[$node] >> $f) - $k;
        $res1 = $coins[$node] >> ($f + 1);
        foreach ($children[$node] as $child) {
            if ($child == $parent) {
                continue;
            }
            $res0 += $this->dfs($child, $node, $f, $coins, $k, $children, $memo);
            if ($f + 1 < 14) {
                $res1 += $this->dfs($child, $node, $f + 1, $coins, $k, $children, $memo);
            }
        }
        $memo[$node][$f] = max($res0, $res1);
        return $memo[$node][$f];
    }
}