Most Profitable Path in a Tree — Medium Problem & Solution

Problem statement

An undirected tree has n nodes labelled 0 to n - 1, rooted at node 0, with edges edges. Every node holds a gate. amount[i] is even: a negative value is the price to open the gate at node i, a positive value is the reward for opening it.

Alice starts at node 0 and Bob at node bob. Every second, Alice moves one step toward some leaf of her choice, and Bob moves one step toward node 0. When either reaches a node whose gate is still closed, they open it and pay or collect amount[i]. If they reach the same node at the same second, they share it: each pays or collects amount[i] / 2. A gate that is already open gives nothing. Alice stops at her leaf; Bob stops at node 0.

Return Alice's maximum possible net income over her choice of leaf.

Example 1

Input: edges = [[0,1],[0,2],[2,3],[2,4]], bob = 4, amount = [2,-6,8,10,-4]
Output: 16
Explanation: Alice goes 0 → 2 → 3: she takes 2 at node 0, shares node 2 with Bob (+4), and takes 10 at node 3.

Example 2

Input: edges = [[0,1]], bob = 1, amount = [-4,6]
Output: -4
Explanation: Bob opens node 1 at second 0, so Alice only pays for node 0.

Example 3

Input: edges = [[0,1],[1,2],[2,3]], bob = 3, amount = [4,-2,6,8]
Output: 2

Constraints

• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges represents a valid tree
• 1 <= bob < n
• amount.length == n
• amount[i] is an even integer in the range [-10^4, 10^4]

How to solve Most Profitable Path in a Tree

Bob's moves are fixed, so for every node we know when (if ever) he opens it. Alice's income along any root-to-leaf path is then a simple prefix sum.

Approach

1. BFS from node 0 to get every node's parent and depth.
2. Walk from bob to the root through the parents, giving each node on the way its Bob time t = 0, 1, 2, …; every other node has Bob time ∞.
3. Process nodes in BFS order: Alice's gain at x is amount[x] if depth[x] < bobTime[x], amount[x] / 2 if they are equal, else 0. Add it to the parent's running income.
4. Return the largest running income among leaves (nodes ≠ 0 with degree 1).

Why it works

Alice moves away from the root one level per second, so she stands on node x exactly at second depth[x]; Bob stands on the nodes of his path at known seconds and never elsewhere. Comparing the two arrival times decides who opens each gate, independent of Alice's later choices, so the income of a leaf is the sum of per-node gains on its root path.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The root is not a leaf even when it has a single neighbour.
• Bob's own path includes node 0; Alice always reaches node 0 first (at second 0), so she takes its full amount.
• The best income may be negative — do not start the maximum at 0.

Reference solution

Python

from typing import List

def mostProfitablePath(edges: List[List[int]], bob: int, amount: List[int]) -> int:
    n = len(amount)
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-1] * n
    depth = [0] * n
    seen = [False] * n
    seen[0] = True
    order = [0]
    for u in order:
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                depth[v] = depth[u] + 1
                order.append(v)
    INF = 10 ** 9
    bob_time = [INF] * n
    x, t = bob, 0
    while x != -1:
        bob_time[x] = t
        t += 1
        x = parent[x]
    income = [0] * n
    best = None
    for u in order:
        if depth[u] < bob_time[u]:
            gain = amount[u]
        elif depth[u] == bob_time[u]:
            gain = amount[u] // 2
        else:
            gain = 0
        income[u] = gain + (income[parent[u]] if u != 0 else 0)
        if u != 0 and len(adj[u]) == 1 and (best is None or income[u] > best):
            best = income[u]
    return best

JavaScript

var mostProfitablePath = function(edges, bob, amount) {
    var n = amount.length;
    var adj = [];
    for (var i = 0; i < n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    var parent = [], depth = [], bobTime = [], income = [];
    for (var k = 0; k < n; k++) { parent.push(-2); depth.push(0); bobTime.push(1000000000); income.push(0); }
    parent[0] = -1;
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var u = order[h];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (parent[v] === -2) { parent[v] = u; depth[v] = depth[u] + 1; order.push(v); }
        }
    }
    for (var x = bob, t = 0; x !== -1; x = parent[x], t++) bobTime[x] = t;
    var best = null;
    for (var q = 0; q < n; q++) {
        var w = order[q];
        var gain = depth[w] < bobTime[w] ? amount[w] : depth[w] === bobTime[w] ? amount[w] / 2 : 0;
        income[w] = gain + (w === 0 ? 0 : income[parent[w]]);
        if (w !== 0 && adj[w].length === 1 && (best === null || income[w] > best)) best = income[w];
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium