⚡Flashcard Drill➔
NeetCode #603LC-2467MediumGraphs
← Back to All Problems

#603 · #2467 · Most Profitable Path in a Tree(树上最大得分和路径)

📌 Problem Statement & Constraints

There is a tree of n nodes rooted at 0. Alice starts at 0 and Bob at bob; both move one edge per second toward node 0, and Bob cannot change direction. Alice earns amount[i] for a node she reaches first, amount[i]/2 if they arrive together, and nothing if Bob arrived first. Return Alice's maximum total income. Constraints: 2 <= n <= 10^5, 1 <= amount[i] <= 1000.

💡 Core Algorithmic Approaches

  1. First find Bob's unique path to the root and the time he reaches each node on it.
  2. Then DFS from the root (Alice) tracking her arrival time.
  3. At each node, compare Alice's time with Bob's: strictly earlier earns the full amount, equal earns half, later earns nothing.
  4. Alice's income is maximised by choosing the best root-to-leaf path, which the DFS explores exhaustively.

💻 Benchmark Python3 Implementation

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        from collections import defaultdict
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        # 1) Bob's path to the root, with arrival times
        def find_path(node: int, parent: int, path: list) -> bool:
            path.append(node)
            if node == 0:
                return True
            for nxt in g[node]:
                if nxt != parent and find_path(nxt, node, path):
                    return True
            path.pop()                     # dead end -> backtrack
            return False

        path = []
        find_path(bob, -1, path)
        bob_time = {node: t for t, node in enumerate(path)}

        # 2) DFS from the root as Alice
        self.best = float("-inf")

        def dfs(node: int, parent: int, t: int, income: int) -> None:
            bt = bob_time.get(node)
            if bt is None or t < bt:
                income += amount[node]     # Alice arrives first
            elif t == bt:
                income += amount[node] // 2   # they arrive together
            # t > bt: Bob already took it
            children = [nxt for nxt in g[node] if nxt != parent]
            if not children:               # a leaf -> the path ends here
                self.best = max(self.best, income)
                return
            for nxt in children:
                dfs(nxt, node, t + 1, income)

        dfs(0, -1, 0, 0)
        return self.best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two traversals of the tree.
💾 Space Complexity
O(n) for the adjacency list and the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Not backtracking in find_path: the path would contain dead-end branches.
  • Only updating the best at leaves: Alice must end at a leaf, since she keeps moving -- the leaf check is required here (unlike the gold-mine problem).
  • Comparing times with <=: the equal case earns half, not the full amount.
  • Forgetting that Bob stops at the root: his time there is the path length, and Alice arrives at time 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems