Problem of The Day: Most Profitable Path in a Tree
Problem Statement
Brute Force [Accepted]
from collections import deque
from typing import List
class Solution:
def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
N = len(amount)
graph = {i: [] for i in range(N)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# --- Phase 1: Find Bob's unique path from node 0 to bob ---
queue = deque([[0, [0]]]) # state: [current_node, path_so_far]
visited = set()
bob_path = []
while queue:
node, path = queue.popleft()
if node in visited:
continue
visited.add(node)
if node == bob:
bob_path = path
break
for nei in graph[node]:
if nei not in visited:
queue.append([nei, path + [nei]])
# Precompute Bob's arrival times for nodes on his path.
# Bob starts at bob (time 0) and moves to 0.
# For a node at index i in bob_path (from 0 to bob),
# Bob arrives at time = (len(bob_path) - 1 - i)
bob_arrival = {}
b = len(bob_path) - 1
for i, node in enumerate(bob_path):
bob_arrival[node] = b - i
# --- Phase 2: Simulate Alice's journey with a BFS ---
# For each state, we keep (node, time, current_profit, parent)
# (using parent to avoid going backwards in the tree)
res = float('-inf')
alice_queue = deque()
alice_queue.append((0, 0, 0, -1)) # starting at node 0, time 0, profit 0
while alice_queue:
node, time, curr_profit, parent = alice_queue.popleft()
# Calculate profit at current node.
# If node is on Bob's path, compare arrival times:
if node in bob_arrival:
if time < bob_arrival[node]:
new_profit = curr_profit + amount[node]
elif time == bob_arrival[node]:
new_profit = curr_profit + amount[node] // 2
else:
new_profit = curr_profit # Bob already took it
else:
new_profit = curr_profit + amount[node]
# Check if it's a leaf (neighbors excluding the parent)
children = [nei for nei in graph[node] if nei != parent]
if not children:
res = max(res, new_profit)
else:
for nei in children:
alice_queue.append((nei, time + 1, new_profit, node))
return res
Editorial
Approach 1: Depth-First Search and Breadth-First Search
class Solution:
def __init__(self):
self.bob_path = {}
self.visited = []
self.tree = []
def mostProfitablePath(self, edges, bob, amount):
n = len(amount)
max_income = float("-inf")
self.tree = [[] for _ in range(n)]
self.bob_path = {}
self.visited = [False] * n
node_queue = deque([(0, 0, 0)])
# Form tree with edges
for edge in edges:
self.tree[edge[0]].append(edge[1])
self.tree[edge[1]].append(edge[0])
# Find the path taken by Bob to reach node 0 and the times it takes to get there
self.find_bob_path(bob, 0)
# Breadth First Search
self.visited = [False] * n
while node_queue:
source_node, time, income = node_queue.popleft()
# Alice reaches the node first
if (
source_node not in self.bob_path
or time < self.bob_path[source_node]
):
income += amount[source_node]
# Alice and Bob reach the node at the same time
elif time == self.bob_path[source_node]:
income += amount[source_node] // 2
# Update max value if current node is a new leaf
if len(self.tree[source_node]) == 1 and source_node != 0:
max_income = max(max_income, income)
# Explore adjacent unvisited vertices
for adjacent_node in self.tree[source_node]:
if not self.visited[adjacent_node]:
node_queue.append((adjacent_node, time + 1, income))
# Mark and remove current node
self.visited[source_node] = True
return max_income
# Depth First Search
def find_bob_path(self, source_node, time):
# Mark and set time node is reached
self.bob_path[source_node] = time
self.visited[source_node] = True
# Destination for Bob is found
if source_node == 0:
return True
# Traverse through unvisited nodes
for adjacent_node in self.tree[source_node]:
if not self.visited[adjacent_node]:
if self.find_bob_path(adjacent_node, time + 1):
return True
# If node 0 isn't reached, remove current node from path
self.bob_path.pop(source_node, None)
return False
Approach 2: Two Depth-First Searches
class Solution:
def __init__(self):
self.bob_path = {}
self.visited = []
self.tree = []
self.max_income = float("-inf")
def mostProfitablePath(self, edges, bob, amount):
n = len(amount)
self.tree = [[] for _ in range(n)]
self.bob_path = {}
self.visited = [False] * n
# Form tree with edges
for edge in edges:
self.tree[edge[0]].append(edge[1])
self.tree[edge[1]].append(edge[0])
# Find the path taken by Bob to reach node 0 and the times it takes to get there
self.find_bob_path(bob, 0)
# Find Alice's optimal path
self.visited = [False] * n
self.find_alice_path(0, 0, 0, amount)
return self.max_income
# Depth First Search to find Bob's path
def find_bob_path(self, source_node, time):
# Mark and set time node is reached
self.bob_path[source_node] = time
self.visited[source_node] = True
# Destination for Bob is found
if source_node == 0:
return True
# Traverse through unvisited nodes
for adjacent_node in self.tree[source_node]:
if not self.visited[adjacent_node] and self.find_bob_path(
adjacent_node, time + 1
):
return True
# If node 0 isn't reached, remove current node from path
self.bob_path.pop(source_node, None)
return False
# Depth First Search to find Alice's optimal path
def find_alice_path(self, source_node, time, income, amount):
# Mark node as explored
self.visited[source_node] = True
# Alice reaches the node first
if (
source_node not in self.bob_path
or time < self.bob_path[source_node]
):
income += amount[source_node]
# Alice and Bob reach the node at the same time
elif time == self.bob_path[source_node]:
income += amount[source_node] // 2
# Update max value if current node is a new leaf
if len(self.tree[source_node]) == 1 and source_node != 0:
self.max_income = max(self.max_income, income)
# Traverse through unvisited nodes
for adjacent_node in self.tree[source_node]:
if not self.visited[adjacent_node]:
self.find_alice_path(adjacent_node, time + 1, income, amount)
Approach 3: Depth-First Search
class Solution:
def __init__(self):
self.tree = []
self.distance_from_bob = []
self.n = 0
def mostProfitablePath(self, edges, bob, amount):
self.n = len(amount)
self.tree = [[] for _ in range(self.n)]
self.distance_from_bob = [0] * self.n
# Form tree with edges
for edge in edges:
self.tree[edge[0]].append(edge[1])
self.tree[edge[1]].append(edge[0])
return self.find_paths(0, 0, 0, bob, amount)
# Depth-first Search
def find_paths(self, source_node, parent_node, time, bob, amount):
max_income = 0
max_child = float("-inf")
# Find the node distances from Bob
if source_node == bob:
self.distance_from_bob[source_node] = 0
else:
self.distance_from_bob[source_node] = self.n
for adjacent_node in self.tree[source_node]:
if adjacent_node != parent_node:
max_child = max(
max_child,
self.find_paths(
adjacent_node, source_node, time + 1, bob, amount
),
)
self.distance_from_bob[source_node] = min(
self.distance_from_bob[source_node],
self.distance_from_bob[adjacent_node] + 1,
)
# Alice reaches the node first
if self.distance_from_bob[source_node] > time:
max_income += amount[source_node]
# Alice and Bob reach the node at the same time
elif self.distance_from_bob[source_node] == time:
max_income += amount[source_node] // 2
# Return max income of leaf node
return (
max_income if max_child == float("-inf") else max_income + max_child
)
