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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Most Profitable Path in a Tree

Difficulty: Medium

Problem Description

There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. At every node i, there is a gate. You are also given an array of even integers amount, where amount[i] represents the price needed to open the gate at node i, if amount[i] is negative, or the cash reward obtained on opening the gate at node i, otherwise. The game goes on as follows:

  • Initially, Alice is at node 0 and Bob is at node bob.
  • At every second, Alice and Bob each move to an adjacent node. Alice moves towards some leaf node, while Bob moves towards node 0.
  • For every node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:
    • If the gate is already open, no price will be required, nor will there be any cash reward.
    • If Alice and Bob reach the node simultaneously, they share the price/reward for opening the gate there.
  • If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node 0, he stops moving. Note that these events are independent of each other.

Return the maximum net income Alice can have if she travels towards the optimal leaf node.

Key Insights

  • The problem involves navigating a tree structure while managing costs and rewards.
  • Alice aims to reach a leaf node, while Bob moves towards the root.
  • The simultaneous arrival at nodes requires careful calculation of shared costs/rewards.
  • The traversal can be efficiently managed using Depth-First Search (DFS) or Breadth-First Search (BFS).

Space and Time Complexity

Time Complexity: O(n) - each node is visited once. Space Complexity: O(n) - for storing the tree structure and recursive stack in DFS or queue in BFS.

Solution

To solve the problem, we can represent the tree using an adjacency list. Both Alice and Bob will traverse the tree, with Alice moving towards the leaves and Bob moving towards the root. We can use a Depth-First Search (DFS) to calculate the maximum net income for Alice. The algorithm will:

  1. Construct the tree from the edges.
  2. Perform a DFS to track both Alice’s and Bob’s positions and manage the costs/rewards based on their simultaneous arrivals at nodes.
  3. Return the maximum net income that Alice can achieve at any leaf node.

Code Solutions

def mostProfitablePath(edges, bob, amount):
    from collections import defaultdict, deque
    
    # Build the tree from edges
    tree = defaultdict(list)
    for a, b in edges:
        tree[a].append(b)
        tree[b].append(a)
    
    # Find Bob's path to root
    def find_bob_path(node, parent):
        path = []
        while node != -1:
            path.append(node)
            node = parent[node]
        return path
    
    parent = [-1] * len(amount)
    queue = deque([0])
    visited = {0}
    
    # BFS to find parent references
    while queue:
        node = queue.popleft()
        for neighbor in tree[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    
    bob_path = find_bob_path(bob, parent)
    
    # Calculate Alice's maximum net income
    max_income = float('-inf')
    
    def dfs(node, depth, bob_index):
        nonlocal max_income
        if bob_index < len(bob_path) and bob_path[bob_index] == node:
            # Both arrive at the same time
            income = amount[node] // 2
            bob_index += 1
        else:
            income = amount[node]
        
        # Update max_income if it's a leaf node
        if len(tree[node]) == 1 and node != 0:
            max_income = max(max_income, income)
        
        # Continue DFS
        for neighbor in tree[node]:
            if neighbor != parent[node]:  # Avoid going back to the parent
                dfs(neighbor, depth + 1, bob_index)
    
    dfs(0, 0, 0)
    
    return max_income

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