LeetCode 2467 - Most Profitable Path in a Tree

LeetCode Problem 2467

Difficulty: 🟡 Medium
Topics: Array, Tree, Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem presents a rooted tree with n nodes numbered from 0 to n-1, where node 0 is the root. Each node has a gate that can either cost money to open (negative value) or give a reward (positive value). Alice starts at the root, and Bob starts at a specified node. Both move simultaneously: Alice moves toward a leaf to maximize her net gain, and Bob moves toward the root. If they meet at a node, the gate's cost or reward is shared equally. Once a node's gate is opened, neither can gain or lose from it again.

The input consists of edges, representing the tree structure, bob, which is Bob’s starting node, and amount, indicating the monetary effect at each node. The output is the maximum net income Alice can achieve by choosing the optimal path to a leaf.

Constraints indicate that the tree can be large (up to 10^5 nodes), so any naive solution exploring all paths without optimization will be too slow. Inputs are guaranteed to form a valid tree, and all amount values are even integers. Edge cases include Bob starting near the root, negative rewards, or all positive rewards.

Approaches

Brute Force Approach

The brute-force approach would simulate every possible leaf path for Alice, tracking Bob’s path toward the root. For each path, compute Alice’s net income by checking if Bob has visited the node first, simultaneously, or not at all. This guarantees correctness because it directly calculates Alice's income for all possibilities.

However, the brute-force solution is inefficient because the number of leaf paths in a tree can be exponential in the worst case. This approach does not scale to n = 10^5 nodes.

Optimal Approach

The key insight is to model Bob’s movement as a map from nodes to the time he arrives at each node. We perform a DFS from Bob to the root to record this. Then, we do a DFS from the root for Alice, where we calculate her potential income at each node based on the timing of Bob’s arrival. At each node:

• If Alice arrives before Bob, she collects the full reward or pays the full cost.
• If Alice and Bob arrive simultaneously, she collects or pays half.
• If Bob has already passed, she gains nothing.

We propagate this calculation down to leaves, tracking the maximum income across all leaf paths. This approach is efficient because each node is visited only twice (once in each DFS), yielding linear time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explore all leaf paths, inefficient for large trees
Optimal	O(n)	O(n)	DFS from Bob to root + DFS from root to leaves, linear in tree size

Algorithm Walkthrough

1. Build the adjacency list for the tree from the edges array. This allows efficient traversal.
2. Record Bob’s arrival times. Using a DFS from Bob toward the root, store the number of steps (time) it takes for Bob to reach each node. This will be used to determine gate sharing with Alice.
3. Perform DFS for Alice from the root node. At each step:

• Determine the current time (depth) for Alice.

• Compute Alice’s net gain at the node based on the following rules:

• If Alice arrives before Bob, add the full amount.

• If Alice arrives at the same time as Bob, add half the amount.

• If Alice arrives after Bob, add zero.

4. Continue DFS recursively for all children of the current node.
5. At leaf nodes, update the maximum net income encountered so far.
6. Return the maximum net income after exploring all paths to leaves.

Why it works:

The invariant is that Alice’s net income at any node depends only on her arrival time and Bob’s arrival time. By computing Bob’s time first, we can accurately simulate the simultaneous or sequential gate interactions. DFS ensures we evaluate all leaf paths efficiently.

Python Solution

from typing import List, Dict

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        from collections import defaultdict

        n = len(amount)
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Record Bob's arrival time at each node; -1 if not on path
        bob_time = [-1] * n
        
        def dfs_bob(node: int, parent: int, time: int) -> bool:
            if node == 0:
                bob_time[node] = time
                return True
            for nei in graph[node]:
                if nei != parent and dfs_bob(nei, node, time + 1):
                    bob_time[node] = time
                    return True
            return False
        
        dfs_bob(bob, -1, 0)
        
        max_income = float('-inf')
        
        def dfs_alice(node: int, parent: int, alice_time: int, current_sum: int):
            nonlocal max_income
            # Determine Alice's gain at this node
            if bob_time[node] == -1 or alice_time < bob_time[node]:
                gain = amount[node]
            elif alice_time == bob_time[node]:
                gain = amount[node] // 2
            else:
                gain = 0
            current_sum += gain
            
            # Leaf check
            if len(graph[node]) == 1 and node != 0:
                max_income = max(max_income, current_sum)
                return
            
            for nei in graph[node]:
                if nei != parent:
                    dfs_alice(nei, node, alice_time + 1, current_sum)
        
        dfs_alice(0, -1, 0, 0)
        return max_income

The Python solution first constructs the adjacency list and computes the arrival time of Bob at each node. Alice’s DFS then calculates net income based on timing rules. Leaf nodes update the maximum income. Using defaultdict(list) simplifies adjacency management, and recursive DFS handles tree traversal efficiently.

Go Solution

package main

func mostProfitablePath(edges [][]int, bob int, amount []int) int {
    n := len(amount)
    graph := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    
    bobTime := make([]int, n)
    for i := range bobTime {
        bobTime[i] = -1
    }
    
    var dfsBob func(node, parent, time int) bool
    dfsBob = func(node, parent, time int) bool {
        if node == 0 {
            bobTime[node] = time
            return true
        }
        for _, nei := range graph[node] {
            if nei != parent && dfsBob(nei, node, time+1) {
                bobTime[node] = time
                return true
            }
        }
        return false
    }
    
    dfsBob(bob, -1, 0)
    
    maxIncome := -1 << 60
    
    var dfsAlice func(node, parent, aliceTime, currentSum int)
    dfsAlice = func(node, parent, aliceTime, currentSum int) {
        var gain int
        if bobTime[node] == -1 || aliceTime < bobTime[node] {
            gain = amount[node]
        } else if aliceTime == bobTime[node] {
            gain = amount[node] / 2
        } else {
            gain = 0
        }
        currentSum += gain
        
        if len(graph[node]) == 1 && node != 0 {
            if currentSum > maxIncome {
                maxIncome = currentSum
            }
            return
        }
        
        for _, nei := range graph[node] {
            if nei != parent {
                dfsAlice(nei, node, aliceTime+1, currentSum)
            }
        }
    }
    
    dfsAlice(0, -1, 0, 0)
    return maxIncome
}

The Go implementation mirrors the Python logic. graph is a slice of slices for adjacency, bobTime stores Bob’s arrival, and DFS functions are defined as closures. Leaf detection and gain computation follow the same rules. Go-specific handling includes large negative initialization for maxIncome.

Worked Examples

Example 1: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]

• Bob’s arrival times: [3,2,3,0,1]

• Alice path 0->1->3->4:

• Node 0: Alice arrives first, gain -2 → current sum -2

• Node 1: simultaneous, gain 4/2=2 → current sum 0

• Node 3: Bob arrived earlier, gain 0 → current sum 0

• Node 4: Alice alone, gain 6 → current sum 6

Max income = 6.

Example 2: edges = [[0,1]], bob = 1, amount = [-7280,2350]

• Bob’s arrival: [1,0]

• Alice path 0->1:

• Node