2467.js

/** ------------------------------------------------------------------------------
 * 
 * 2467. Most Profitable Path in a Tree
 * Topics: Tree, DFS
 * https://leetcode.com/problems/most-profitable-path-in-a-tree/?envType=daily-question&envId=2025-02-24
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[][]} edges
 * @param {number} bob
 * @param {number[]} amount
 * @return {number}
 */
var mostProfitablePath = function (edges, bob, amount) {
  const n = amount.length
  const tree = Array.from({ length: n }, () => [])

  for (const [u, v] of edges) {
    tree[u].push(v)
    tree[v].push(u)
  }

  const bobPath = Array(n).fill(-1)

  const dfsBob = (node, parent, time) => {
    bobPath[node] = time
    if (node === 0) return true
    for (const neighbor of tree[node]) {
      if (neighbor !== parent && dfsBob(neighbor, node, time + 1)) {
        return true
      }
    }
    bobPath[node] = -1
    return false
  }
  dfsBob(bob, -1, 0)

  let maxProfit = -Infinity
  const dfsAlice = (node, parent, time, profit) => {
    if (bobPath[node] === -1 || bobPath[node] > time) {
      profit += amount[node]
    } else if (bobPath[node] === time) {
      profit += amount[node] / 2
    }

    const isLeaf = tree[node].every((neighbor) => neighbor === parent)
    if (isLeaf) {
      maxProfit = Math.max(maxProfit, profit)
      return
    }

    for (const neighbor of tree[node]) {
      if (neighbor !== parent) {
        dfsAlice(neighbor, node, time + 1, profit)
      }
    }
  }

  dfsAlice(0, -1, 0, 0)

  return maxProfit
}

const edges = [
  [0, 1],
  [1, 2],
  [1, 3],
  [3, 4],
]
const bob = 3
const amount = [-2, 4, 2, -4, 6]
console.log(mostProfitablePath(edges, bob, amount))