Most Profitable Path in a Tree Python Solution

Tested Python solution for LeetCode 2467 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 2467, Medium. Topics: Array, Tree, Depth-First Search, Breadth-First Search, Graph Theory. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2467   # by problem number
lcpy gen -s most_profitable_path_in_a_tree   # by problem name

​

Problem

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] = [a<sub>i</sub>, b<sub>i</sub>] indicates that there is an edge between nodes a<sub>i</sub> and b<sub>i</sub> 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. In other words, if the price to open the gate is c, then both Alice and Bob pay c / 2 each. Similarly, if the reward at the gate is c, both of them receive c / 2 each.
• 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.

​

Examples

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

Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]
Output: -7280

​

Constraints

• 2 <= n <= 10⁵
• edges.length == n - 1
• edges[i].length == 2
• 0 <= a_i, b_i < n
• a_i != b_i
• edges represents a valid tree.
• 1 <= bob < n
• amount.length == n
• amount[i] is an even integer in the range [-10⁴, 10⁴].

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(n)
    def most_profitable_path(self, edges: list[list[int]], bob: int, amount: list[int]) -> int:
        n = len(amount)
        adj: list[list[int]] = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        depth = [0] * n
        parent = [-1] * n
        order = [0]
        for u in order:
            for v in adj[u]:
                if v != parent[u]:
                    parent[v] = u
                    depth[v] = depth[u] + 1
                    order.append(v)

        bob_time: dict[int, int] = {}
        node, t = bob, 0
        while True:
            bob_time[node] = t
            if node == 0:
                break
            node = parent[node]
            t += 1

        gain = [0] * n
        for u in reversed(order):
            child_best = max((gain[v] for v in adj[u] if v != parent[u]), default=0)
            gate = amount[u]
            bt = bob_time.get(u, -1)
            if bt == -1 or bt > depth[u]:
                pass
            elif bt == depth[u]:
                gate = amount[u] // 2
            else:
                gate = 0
            gain[u] = gate + child_best
        return gain[0]

​

Complexity

Time	Space
O(n)	O(n)

​

Tags

NeetCode All.