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
- First find Bob's unique path to the root and the time he reaches each node on it.
- Then DFS from the root (Alice) tracking her arrival time.
- At each node, compare Alice's time with Bob's: strictly earlier earns the full amount, equal earns half, later earns nothing.
- 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.