2564. Most Profitable Path in a Tree

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        from collections import defaultdict, deque
        
        n = len(amount)
        graph = defaultdict(list)
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        # Find path from bob to 0 using BFS and track parent
        parent = [-1] * n
        visited = [False] * n
        queue = deque([bob])
        visited[bob] = True
        
        while queue:
            node = queue.popleft()
            if node == 0:
                break
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    parent[neighbor] = node
                    queue.append(neighbor)
        
        # Build bob's path and timing
        bob_time = {}
        time = 0
        curr = bob
        while curr != -1:
            bob_time[curr] = time
            curr = parent[curr] if curr != 0 else -1
            time += 1
            if curr == -1 and 0 in bob_time:
                break
            if curr == -1:
                # Bob doesn't reach 0, rebuild path
                break
        
        # Rebuild bob's path correctly
        bob_time = {}
        time = 0
        path = [bob]
        curr = bob
        while curr != 0:
            for neighbor in graph[curr]:
                if visited[neighbor] and parent[curr] != neighbor and (neighbor == 0 or parent[neighbor] == curr):
                    # Need to use BFS to find path from bob to 0
                    pass
            break
        
        # Use DFS from 0 to find bob's path
        def find_path_to_bob(node, par, path):
            if node == bob:
                return True
            for neighbor in graph[node]:
                if neighbor != par:
                    path.append(neighbor)
                    if find_path_to_bob(neighbor, node, path):
                        return True
                    path.pop()
            return False
        
        bob_path = [0]
        find_path_to_bob(0, -1, bob_path)
        bob_path.reverse()  # Now path is from bob to 0
        
        bob_time = {node: t for t, node in enumerate(bob_path)}
        
        # DFS from 0, Alice explores all leaf paths
        max_income = float('-inf')
        
        def dfs(node, par, time, income):
            nonlocal max_income
            
            # Calculate income at current node
            if node not in bob_time:
                # Bob doesn't visit this node
                income += amount[node]
            elif bob_time[node] > time:
                # Alice arrives before Bob
                income += amount[node]
            elif bob_time[node] == time:
                # Arrive at same time
                income += amount[node] // 2
            # If bob_time[node] < time, Bob arrived first, income += 0
            
            # Check if leaf node (only connected to parent)
            is_leaf = True
            for neighbor in graph[node]:
                if neighbor != par:
                    is_leaf = False
                    dfs(neighbor, node, time + 1, income)
            
            if is_leaf:
                max_income = max(max_income, income)
        
        dfs(0, -1, 0, 0)
        return max_income