There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. 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. At every node i

mostProfitablePath.js

/**
 * @param {number[][]} edges
 * @param {number} bob
 * @param {number[]} amount
 * @return {number}
 */
var mostProfitablePath = function(edges, bob, amount) {
    const n = amount.length;
    const graph = new Map();

    // Build the tree using an adjacency list
    for (let edge of edges) {
        const [a, b] = edge;
        if (!graph.has(a)) {
            graph.set(a, []);
        }
        if (!graph.has(b)) {
            graph.set(b, []);
        }
        graph.get(a).push(b);
        graph.get(b).push(a);
    }

    // Array to keep track of the step at which Bob arrives at each node
    const stepsBob = new Array(n).fill(n);

    let aliceScore = amount[0];
    let maxScore = -Infinity;

    // Function to backtrack and calculate the step at which Bob arrives at each node
    function backtrack(step, node, prev_node) {
        if (node === 0) {
            stepsBob[node] = step;
            return true;
        }

        for (let neigh of graph.get(node)) {
            // Since it's a tree, don't visit the previous node
            if (neigh !== prev_node) {
                if (backtrack(step + 1, neigh, node)) {
                    stepsBob[node] = step;
                    return true;
                }
            }
        }
        return false;
    }

    // Function to backtrack and calculate Alice's maximum net income
    function backtrackAlice(node, step, score, prev_node) {
        // If it's a leaf node, return the score
        if (graph.get(node).length === 1 && node !== 0) {
            return score;
        }

        for (let neigh of graph.get(node)) {
            // Since it's a tree, don't visit the previous node
            if (neigh !== prev_node) {
                let modifier = 0;
                // If Bob and Alice arrive at the same time, they split the amount
                if (step === stepsBob[neigh]) {
                    modifier = amount[neigh] / 2;
                } else if (step < stepsBob[neigh]) {
                    // If Alice arrives earlier than Bob, she gets the full amount
                    modifier = amount[neigh];
                }

                score += modifier;
                maxScore = Math.max(backtrackAlice(neigh, step + 1, score, node), maxScore);
                score -= modifier;
            }
        }

        return maxScore;
    }

    // Calculate the steps at which Bob arrives at each node
    backtrack(0, bob, -1);

    // Calculate Alice's maximum net income
    backtrackAlice(0, 1, aliceScore, -1);

    return maxScore;
};