Most Profitable Path in a Tree

Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
Output: 6
Explanation: 
The above diagram represents the given tree. The game goes as follows:
- Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes.
  Alice's net income is now -2.
- Both Alice and Bob move to node 1. 
  Since they reach here simultaneously, they open the gate together and share the reward.
  Alice's net income becomes -2 + (4 / 2) = 0.
- Alice moves on to node 3. Since Bob already opened its gate, Alice's income remains unchanged.
  Bob moves on to node 0, and stops moving.
- Alice moves on to node 4 and opens the gate there. Her net income becomes 0 + 6 = 6.
Now, neither Alice nor Bob can make any further moves, and the game ends.
It is not possible for Alice to get a higher net income.

Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]
Output: -7280
Explanation: 
Alice follows the path 0->1 whereas Bob follows the path 1->0.
Thus, Alice opens the gate at node 0 only. Hence, her net income is -7280. 

class Solution {
    // Represents the tree as an adjacency list
    private List<List<Integer>> tree;
    
    // Tracks when Bob reaches each node
    private Map<Integer, Integer> bobTime;
    
    // Tracks visited nodes during DFS
    private boolean[] visited;
    
    // Stores the profit or loss at each node
    private int[] amount;
    
    // Stores the maximum income Alice can achieve
    private int maxIncome = Integer.MIN_VALUE;

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = amount.length;
        
        // Initialize adjacency list for the tree
        tree = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }

        // Build the tree from the provided edges
        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]); // Add edge in both directions
            tree.get(edge[1]).add(edge[0]);
        }

        // Initialize bobTime map and visited array
        bobTime = new HashMap<>();
        visited = new boolean[n];
        
        // Perform DFS to calculate Bob's arrival times
        dfsBob(bob, 0);

        // Store the `amount` array for Alice's traversal
        this.amount = amount;
        
        // Reset visited array for Alice's DFS
        Arrays.fill(visited, false);
        
        // Perform DFS for Alice's traversal, starting from the root (node 0)
        dfsAlice(0, 0, 0);

        // Return the maximum income Alice can achieve
        return maxIncome;
    }

    // DFS to calculate when Bob reaches each node
    private boolean dfsBob(int node, int time) {
        bobTime.put(node, time); // Record the time Bob reaches this node
        visited[node] = true; // Mark node as visited
        
        // If Bob reaches the root, we are done
        if (node == 0) {
            return true;
        }

        // Explore neighbours recursively
        for (int nei : tree.get(node)) {
            if (!visited[nei]) { // Only visit unvisited nodes
                if (dfsBob(nei, time + 1)) { // Recur for connected nodes
                    return true; // If root is reached, stop recursion
                }
            }
        }

        // If path to root doesn't exist through this node, remove it from bobTime
        bobTime.remove(node);
        return false;
    }

    // DFS to calculate Alice's maximum income
    private void dfsAlice(int node, int time, int income) {
        visited[node] = true; // Mark node as visited

        // Update income based on Alice and Bob's arrival times
        if (!bobTime.containsKey(node) || time < bobTime.get(node)) {
            // If Alice reaches first or Bob never visits the node
            income += amount[node]; 
        } else if (time == bobTime.get(node)) {
            // If Alice and Bob arrive simultaneously, they share the amount
            income += amount[node] / 2;
        }

        // If Alice reaches a leaf node, update the maximum income
        if (tree.get(node).size() == 1 && node != 0) { // Skip root as leaf node
            maxIncome = Math.max(maxIncome, income);
        }

        // Recur for all unvisited neighbours
        for (int nei : tree.get(node)) {
            if (!visited[nei]) {
                dfsAlice(nei, time + 1, income); // Recur for next node
            }
        }
    }
}

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        n = len(amount)  # Number of nodes
        tree = [[] for _ in range(n)]  # Adjacency list representation of the tree
        
        # Build the adjacency list
        for a, b in edges:
            tree[a].append(b)
            tree[b].append(a)
        
        bobTime = {}  # Stores the time Bob reaches each node
        visited = [False] * n  # Tracks visited nodes for DFS
        maxIncome = float('-inf')  # Stores the maximum income Alice can achieve

        # Nested function for Bob's DFS
        def dfsBob(node: int, time: int) -> bool:
            nonlocal bobTime
            bobTime[node] = time  # Record Bob's arrival time
            visited[node] = True  # Mark node as visited
            
            if node == 0:  # If Bob reaches the root, stop
                return True
            
            for nei in tree[node]:
                if not visited[nei]:  # Traverse unvisited neighbours
                    if dfsBob(nei, time + 1):
                        return True
            
            bobTime.pop(node)  # Remove node if it doesn't lead to the root
            return False

        # Nested function for Alice's DFS
        def dfsAlice(node: int, time: int, income: int):
            nonlocal maxIncome
            visited[node] = True  # Mark node as visited

            # Calculate Alice's income based on interaction with Bob
            if node not in bobTime or time < bobTime[node]:
                income += amount[node]  # Alice reaches first
            elif time == bobTime[node]:
                income += amount[node] // 2  # Alice and Bob arrive simultaneously

            # Update maximum income if node is a leaf
            if len(tree[node]) == 1 and node != 0:  # Leaf node check
                maxIncome = max(maxIncome, income)

            for nei in tree[node]:
                if not visited[nei]:  # Traverse unvisited neighbours
                    dfsAlice(nei, time + 1, income)

        # Perform DFS for Bob starting at `bob`
        dfsBob(bob, 0)

        # Reset visited array for Alice's traversal
        visited = [False] * n

        # Perform DFS for Alice starting at the root (node 0)
        dfsAlice(0, 0, 0)

        return maxIncome