Most Profitable Path in a Tree

medium tree dfs bfs

Problem

An undirected tree of n nodes is rooted at node 0. Each node i has a gate with an even value amount[i]: a cost if negative, a reward if positive. Alice starts at node 0 and walks toward some leaf; Bob starts at node bob and walks toward node 0. Each second both move one edge. A node's value is collected by whoever arrives first; if Alice and Bob arrive at the same second they split it. Return the maximum net income Alice can earn over all leaf choices.

Inputedges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]

Output6

Alice 0→1→3→4. She pays −2 at node 0, shares node 1's +4 with Bob (+2), node 3 was already opened by Bob, then takes +6 at leaf 4: −2 + 2 + 0 + 6 = 6.

edges (a:b, comma-separated)

bob (start node)

amount (comma-separated, even)

def most_profitable_path(edges, bob, amount):
    n = len(amount)
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)
    parent = [-1] * n
    def set_parents(u, p):
        parent[u] = p
        for v in g[u]:
            if v != p:
                set_parents(v, u)
    set_parents(0, -1)
    bob_time = {}
    t, v = 0, bob
    while v != -1:
        bob_time[v] = t
        v, t = parent[v], t + 1
    best = [float("-inf")]
    def dfs(u, p, time, income):
        if u not in bob_time or time < bob_time[u]:
            income += amount[u]
        elif time == bob_time[u]:
            income += amount[u] // 2
        leaf = True
        for v in g[u]:
            if v != p:
                leaf = False
                dfs(v, u, time + 1, income)
        if leaf:
            best[0] = max(best[0], income)
    dfs(0, -1, 0, 0)
    return best[0]

function mostProfitablePath(edges, bob, amount) {
  const n = amount.length;
  const g = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { g[a].push(b); g[b].push(a); }
  const parent = new Array(n).fill(-1);
  const setParents = (u, p) => {
    parent[u] = p;
    for (const v of g[u]) if (v !== p) setParents(v, u);
  };
  setParents(0, -1);
  const bobTime = new Map();
  for (let v = bob, t = 0; v !== -1; v = parent[v], t++) bobTime.set(v, t);
  let best = -Infinity;
  const dfs = (u, p, time, income) => {
    if (!bobTime.has(u) || time < bobTime.get(u)) income += amount[u];
    else if (time === bobTime.get(u)) income += amount[u] / 2;
    let leaf = true;
    for (const v of g[u]) if (v !== p) { leaf = false; dfs(v, u, time + 1, income); }
    if (leaf) best = Math.max(best, income);
  };
  dfs(0, -1, 0, 0);
  return best;
}

int mostProfitablePath(int[][] edges, int bob, int[] amount) {
    int n = amount.length;
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
    int[] parent = new int[n];
    setParents(g, 0, -1, parent);
    Map<Integer, Integer> bobTime = new HashMap<>();
    for (int v = bob, t = 0; v != -1; v = parent[v], t++) bobTime.put(v, t);
    best = Integer.MIN_VALUE;
    dfs(g, 0, -1, 0, 0, amount, bobTime);
    return best;
}
int best;
void setParents(List<List<Integer>> g, int u, int p, int[] parent) {
    parent[u] = p;
    for (int v : g.get(u)) if (v != p) setParents(g, v, u, parent);
}
void dfs(List<List<Integer>> g, int u, int p, int time, int income,
         int[] amount, Map<Integer, Integer> bobTime) {
    if (!bobTime.containsKey(u) || time < bobTime.get(u)) income += amount[u];
    else if (time == bobTime.get(u)) income += amount[u] / 2;
    boolean leaf = true;
    for (int v : g.get(u)) if (v != p) { leaf = false; dfs(g, v, u, time + 1, income, amount, bobTime); }
    if (leaf) best = Math.max(best, income);
}

int best;
vector<vector<int>> g;
void setParents(int u, int p, vector<int>& parent) {
    parent[u] = p;
    for (int v : g[u]) if (v != p) setParents(v, u, parent);
}
void dfs(int u, int p, int time, int income,
         vector<int>& amount, unordered_map<int,int>& bobTime) {
    auto it = bobTime.find(u);
    if (it == bobTime.end() || time < it->second) income += amount[u];
    else if (time == it->second) income += amount[u] / 2;
    bool leaf = true;
    for (int v : g[u]) if (v != p) { leaf = false; dfs(v, u, time + 1, income, amount, bobTime); }
    if (leaf) best = max(best, income);
}
int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
    int n = amount.size();
    g.assign(n, {});
    for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
    vector<int> parent(n);
    setParents(0, -1, parent);
    unordered_map<int,int> bobTime;
    for (int v = bob, t = 0; v != -1; v = parent[v], t++) bobTime[v] = t;
    best = INT_MIN;
    dfs(0, -1, 0, 0, amount, bobTime);
    return best;
}

Explanation

The key insight is that Bob's path is fixed: he can only walk from his start node toward the root along the unique tree path. So we precompute, for every node on that path, the exact second Bob reaches it — call it bobTime[node].

To follow parent pointers up to the root, we first root the tree at node 0 with a DFS (setParents) that records each node's parent. Then walking from bob via parent until we hit −1 gives us Bob's timeline.

Alice's exploration is a DFS from node 0 carrying the current time and accumulated income. At each node we compare Alice's arrival time with Bob's: if Bob never visits the node or Alice arrives strictly earlier, Alice collects the full amount; if they arrive at the same second, she takes half; if Bob arrives first, the gate is already open so she gets nothing.

Because Alice must stop at a leaf, we only update the answer best when the current node has no unvisited children — that is exactly a leaf in the rooted tree. Each leaf represents one complete path Alice could take.

In the default example, the leaf paths from 0 are 0→1→2 and 0→1→3→4. The second path yields −2 + 2 + 0 + 6 = 6, which beats 0→1→2's −2 + 2 + 2 = 2, so the answer is 6.

Both the parent DFS and Alice's DFS visit each node once, so the whole algorithm is linear in the number of nodes.

Time: O(n) Space: O(n)