Most Profitable Path in a Tree

main.md

Question

Approach

I first constructed a graph representation of the tree using an adjacency list. Then I started by determining Bob's exact path from his initial position to the root (node 0). Using a breadth-first search (BFS), I established the parent-child relationships within the tree. With this information, I traced Bob's route back to the root, storing the step count for each node on his path. This step count helped me handle scenarios where Alice and Bob might meet at a node.

To calculate Alice's maximum income, I implemented a depth-first search (DFS) to explore all possible paths Alice could take towards a leaf node. During this traversal, I managed the income calculations by checking whether Alice reached a node before, after, or at the same time as Bob. If they reached a node simultaneously, I halved the reward or cost at that gate. For leaf nodes, I directly returned the accumulated income, while for non-leaf nodes, I recursively computed the best possible income by exploring each branch.

Finally, I initiated the DFS from the root (node 0) and computed the maximum income Alice could achieve.

Implementation

from collections import defaultdict, deque

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        n = len(amount)
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        parent = [-1] * n
        queue = deque([0])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor != parent[node]:
                    parent[neighbor] = node
                    queue.append(neighbor)

        bob_path = [-1] * n
        curr = bob
        steps = 0
        while curr != -1:
            bob_path[curr] = steps
            curr = parent[curr]
            steps += 1

        def dfs(node: int, steps: int) -> int:
            income = 0
            if bob_path[node] == -1 or steps < bob_path[node]:
                income += amount[node]
            elif steps == bob_path[node]:
                income += amount[node] // 2

            max_profit = float('-inf')
            is_leaf = True
            for neighbor in graph[node]:
                if neighbor != parent[node]:
                    is_leaf = False
                    max_profit = max(max_profit, dfs(neighbor, steps + 1))

            if is_leaf:
                return income
            return income + max_profit

        # Start DFS from the root
        max_income = dfs(0, 0)
        return max_income

Complexities

• Time: O(n)
• Space: O(n)