We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Most Profitable Path in a Tree

Number: 2564

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Intuit

Problem Description

Given an undirected tree with n nodes (labeled 0 to n-1) rooted at 0, each node i has a gate with an associated even integer value from the array amount. If amount[i] is negative, it is the cost to open the gate; if positive, it is the cash reward. Two players, Alice and Bob, traverse the tree simultaneously—with Alice starting from node 0 moving toward a leaf and Bob starting from node bob moving toward node 0. At each node, if a player reaches the gate first, she either pays the entire cost or collects the full reward. If they reach a node at the same time, they share the cost or reward equally. Once a gate is open, it remains so. The goal is to calculate the maximum net income Alice can get if she chooses the optimal leaf path.

Key Insights

  • The tree is unweighted; both Alice and Bob move one step per second.
  • Bob moves along the unique path from his starting node to node 0; his arrival times at nodes can be precomputed by backtracking using parent pointers.
  • As Alice traverses from the root to a leaf, at each node, her profit is determined by comparing her arrival time with Bob’s:
    • If Alice arrives before Bob, the full amount is counted.
    • If they arrive simultaneously, half the amount is counted.
    • If Bob arrives first, Alice gains nothing from that node.
  • A DFS from the root computes the maximum cumulative profit along all root-to-leaf paths using the above rule.

Space and Time Complexity

Time Complexity: O(n) – Both BFS for precomputations and DFS for path exploration traverse each node once. Space Complexity: O(n) – Required for storing the tree representation, parent pointers, and Bob’s arrival times.

Solution

We first build an adjacency list for the tree from the edges. A BFS (or DFS) from the root is used to compute parent relationships, allowing us to trace Bob’s unique path from his starting node to the root and record his arrival time at each node. With Bob’s arrival times stored in an array, we perform a DFS from the root (Alice’s starting point), tracking the time (depth) along the path. At each node, we adjust Alice’s cumulative profit:

  • If Alice arrives before Bob, add the full amount.
  • If they arrive simultaneously, add half of the amount.
  • Otherwise (Bob arrived earlier) add nothing. For each leaf reached by Alice, we update the maximum profit. Finally, the solution returns the maximum profit found.

Code Solutions

def mostProfitablePath(edges, bob, amount):
    from collections import defaultdict, deque
    n = len(amount)
    # Build the tree as an adjacency list
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    # Compute parent pointers and depth via BFS from the root (node 0)
    parent = [-1] * n
    depth = [0] * n
    q = deque([0])
    while q:
        node = q.popleft()
        for neighbor in tree[node]:
            if neighbor == parent[node]:
                continue
            parent[neighbor] = node
            depth[neighbor] = depth[node] + 1
            q.append(neighbor)
    
    # Compute Bob's arrival times along his unique path from bob to 0
    INF = float('inf')
    bob_time = [INF] * n
    t = 0
    node = bob
    while node != -1:
        bob_time[node] = t
        t += 1
        node = parent[node]
    
    res = -10**9
    # DFS to explore all paths from the root to leaves
    def dfs(node, par, time, curr_sum):
        nonlocal res
        # Update current sum based on the timing comparison
        if time < bob_time[node]:
            curr_sum += amount[node]
        elif time == bob_time[node]:
            curr_sum += amount[node] // 2
        # Flag to check if node is a leaf
        isLeaf = True
        for neighbor in tree[node]:
            if neighbor == par:
                continue
            isLeaf = False
            dfs(neighbor, node, time + 1, curr_sum)
        if isLeaf:
            res = max(res, curr_sum)
    
    dfs(0, -1, 0, 0)
    return res

# Example usage:
print(mostProfitablePath([[0,1],[1,2],[1,3],[3,4]], 3, [-2,4,2,-4,6]))
← Back to All Questions