# Most Profitable Path in a Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/most-profitable-path-in-a-tree)
Canonical: https://scaleengineer.com/dsa/problems/most-profitable-path-in-a-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Tree, Graph
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## Problem
There is an undirected tree with `n` nodes labeled from `0` to `n - 1`, rooted at node `0`. You are given a 2D integer array `edges` of length `n - 1` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

At every node `i`, there is a gate. You are also given an array of even integers `amount`, where `amount[i]` represents:

* the price needed to open the gate at node `i`, if `amount[i]` is negative, or,
* the cash reward obtained on opening the gate at node `i`, otherwise.

The game goes on as follows:

* Initially, Alice is at node `0` and Bob is at node `bob`.
* At every second, Alice and Bob **each** move to an adjacent node. Alice moves towards some **leaf node**, while Bob moves towards node `0`.
* For **every** node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:  
  * If the gate is **already open**, no price will be required, nor will there be any cash reward.
  * If Alice and Bob reach the node **simultaneously**, they share the price/reward for opening the gate there. In other words, if the price to open the gate is `c`, then both Alice and Bob pay `c / 2` each. Similarly, if the reward at the gate is `c`, both of them receive `c / 2` each.
* If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node `0`, he stops moving. Note that these events are **independent** of each other.

Return _the **maximum** net income Alice can have if she travels towards the optimal leaf node._

**Example 1:**

![](https://assets.glich.co/dsa/most-profitable-path-in-a-tree/image0.png) 

**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.

**Example 2:**

![](https://assets.glich.co/dsa/most-profitable-path-in-a-tree/image1.png) 

**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. 

**Constraints:**

* `2 <= n <= 105`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `0 <= ai, bi < n`
* `ai != bi`
* `edges` represents a valid tree.
* `1 <= bob < n`
* `amount.length == n`
* `amount[i]` is an **even** integer in the range `[-104, 104]`.

# Approaches
## Brute Force per Leaf Path
This approach directly simulates the problem by considering every possible path Alice can take. It works by first identifying all leaf nodes in the tree. For each leaf, it constructs the path from the root (Alice's start) to that leaf. It also determines Bob's fixed path from his starting location to the root. By comparing their arrival times at each node on Alice's path, it calculates the total income for that specific route. The final answer is the maximum income found across all possible leaf-bound paths.
**Time:** O(N^2) in the worst case. Finding parent pointers is O(N). Finding Bob's path is O(N). However, there can be up to O(N) leaves. For each leaf, tracing Alice's path and calculating the income takes O(N) time. This results in a total complexity dominated by O(Leaves * N), which is O(N^2) in the worst case (e.g., a star graph). · **Space:** O(N), where N is the number of nodes. This space is used for the adjacency list, parent array, storing Bob's path timings, and the list of leaves.
**Pros:** Conceptually simple and easy to understand.; Correctly solves the problem for small inputs by exhaustively checking each of Alice's goal-oriented paths.
**Cons:** Highly inefficient for large trees, with a time complexity of O(N^2), which will likely result in a 'Time Limit Exceeded' error on larger test cases.; Involves redundant computations, as information about Bob's path and timings is re-evaluated for each of Alice's potential paths.
### Explanation
The core idea is to break down the problem into smaller, independent calculations for each of Alice's possible destinations. We treat each path from the root to a leaf as a separate scenario. For each scenario, we perform a full calculation of the income. 

First, we need a way to determine paths. A simple method is to root the tree at node 0 and find the parent of every other node. This can be done with a single traversal (BFS or DFS). Once we have parent pointers, we can trace the path from any node back to the root.

With the ability to find paths, we first determine Bob's fixed path and the time he takes to reach each node on it. Then, we loop through all leaf nodes. For each leaf, we trace Alice's path and, node by node, compare her travel time against Bob's to calculate her income. This process is repeated for all leaves, and the best outcome is recorded.

```java
// Note: This is a simplified conceptual implementation for demonstration.
// A full implementation would require helper methods for pathfinding.
import java.util.*;

class Solution {
    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = amount.length;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    parent[v] = u;
                    q.offer(v);
                }
            }
        }

        Map<Integer, Integer> bobTimes = new HashMap<>();
        int curr = bob;
        int time = 0;
        while (curr != -1) {
            bobTimes.put(curr, time++);
            curr = parent[curr];
        }

        List<Integer> leaves = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            if (adj[i].size() == 1) {
                leaves.add(i);
            }
        }
        if (n > 0 && adj[0].size() == 0) { // Case where root is a leaf (n=1)
             leaves.add(0);
        } else if (n==2 && adj[0].size() == 1) { // Case for n=2
             leaves.add(1);
        }

        int maxIncome = Integer.MIN_VALUE;

        for (int leaf : leaves) {
            List<Integer> alicePath = new ArrayList<>();
            curr = leaf;
            while (curr != -1) {
                alicePath.add(curr);
                curr = parent[curr];
            }
            Collections.reverse(alicePath);

            int currentIncome = 0;
            for (int i = 0; i < alicePath.size(); i++) {
                int u = alicePath.get(i);
                int aliceTime = i;
                int bobTime = bobTimes.getOrDefault(u, Integer.MAX_VALUE);

                if (aliceTime < bobTime) {
                    currentIncome += amount[u];
                } else if (aliceTime == bobTime) {
                    currentIncome += amount[u] / 2;
                }
            }
            maxIncome = Math.max(maxIncome, currentIncome);
        }

        return maxIncome;
    }
}
```
### Algorithm
*   **Build Graph and Parent Pointers:** Construct an adjacency list for the tree. Then, run a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from the root (node 0) to compute a `parent` array. This array allows us to easily trace the shortest path from any node back to the root.
*   **Identify All Leaf Nodes:** Traverse all nodes to find the ones that are leaves. A node `i` (where `i != 0`) is a leaf if it has only one connection (degree 1).
*   **Determine Bob's Path and Timings:** Using the `parent` array, trace Bob's path from his starting node `bob` to the root `0`. Store the time it takes him to reach each node on this path in a map or an array. For any node `u` on his path, the time is its distance from `bob` along this path.
*   **Iterate Through Alice's Paths:** For each leaf node `L` identified earlier:
    1.  Determine Alice's unique path from `0` to `L` using the `parent` array.
    2.  Initialize a `current_income` for this path to 0.
    3.  Iterate through each node `u` on Alice's path. Let her arrival time be `time_A` (her distance from the root).
    4.  Look up Bob's arrival time `time_B` for node `u` from the pre-calculated data.
    5.  Calculate Alice's gain at node `u`:
        *   If `time_A < time_B`, she arrives first and gets the full `amount[u]`.
        *   If `time_A == time_B`, they arrive together, and she gets `amount[u] / 2`.
        *   If `time_A > time_B`, Bob arrives first, so she gets `0`.
    6.  Add this gain to `current_income`.
*   **Find Maximum Income:** Keep track of the maximum `current_income` found among all paths to leaves. This maximum value is the result.

## Single DFS with Pre-computation of Bob's Path
This optimal approach avoids redundant calculations by first pre-computing all necessary information about Bob's movement. It determines Bob's unique path to the root and the exact time he arrives at each node on that path. This data is stored in an array. With this information, a single Depth-First Search (DFS) from the root (Alice's starting point) is sufficient to find the best path. As the DFS explores paths towards leaves, it uses the pre-computed `bobTime` array to instantly calculate Alice's income at each node by comparing her travel time (the DFS depth) with Bob's. This way, all possible paths are evaluated efficiently in one traversal.
**Time:** O(N), where N is the number of nodes. Building the graph is O(N). The BFS to find parents is O(N). Calculating Bob's timings takes O(N). The final DFS visits each node and edge once, also taking O(N). The total time complexity is O(N). · **Space:** O(N), where N is the number of nodes. Space is required for the adjacency list, the `parent` array, the `bobTime` array, and the recursion stack for the DFS (which can go up to depth N in the worst case).
**Pros:** Optimal solution with linear time complexity, making it very efficient for large inputs.; Avoids redundant work by pre-calculating Bob's path information once.; Elegantly solves the problem with a single main traversal (DFS) after the setup.
**Cons:** The implementation is slightly more involved than a simple brute-force approach due to the pre-computation step.
### Explanation
The efficiency of this method comes from processing Bob's and Alice's movements in separate, optimized stages. 

**Stage 1: Analyze Bob's Movement.** Since Bob's path is fixed (always moving towards the root), we can determine it once. We run a BFS from the root `0` to establish parent pointers for the entire tree. Then, starting from `bob`, we walk up the tree using these pointers, recording the time taken (distance from `bob`) at each step in a `bobTime` array. Nodes not on Bob's path will have an infinite travel time for him.

**Stage 2: Find Alice's Optimal Path.** We perform a DFS starting from `0`. The DFS naturally explores all of Alice's possible paths to leaf nodes. The parameters of our DFS function will be `(currentNode, parentNode, aliceTime, currentPathIncome)`. At each node, we calculate the income based on `aliceTime` and the pre-computed `bobTime[currentNode]`. When the DFS reaches a leaf node (a node with no children other than its parent), we compare its path's total income with our global maximum and update it if necessary. This ensures we find the most profitable path in a single pass over the tree.

```java
import java.util.*;

class Solution {
    List<Integer>[] adj;
    int[] amount;
    int[] bobTime;
    int maxIncome = Integer.MIN_VALUE;

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = amount.length;
        this.adj = new ArrayList[n];
        this.amount = amount;
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        // Step 1: Find Bob's path and timings
        this.bobTime = new int[n];
        Arrays.fill(bobTime, Integer.MAX_VALUE);
        
        // Find parent pointers to trace Bob's path from bob to 0
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n];
        
        q.offer(0);
        visited[0] = true;
        
        while(!q.isEmpty()){
            int u = q.poll();
            for(int v : adj[u]){
                if(!visited[v]){
                    visited[v] = true;
                    parent[v] = u;
                    q.offer(v);
                }
            }
        }

        // Trace Bob's path and record time
        int curr = bob;
        int time = 0;
        while (curr != -1) {
            bobTime[curr] = time;
            curr = parent[curr];
            time++;
        }

        // Step 2: DFS for Alice to find max income
        dfs(0, -1, 0, 0);

        return maxIncome;
    }

    private void dfs(int u, int p, int aliceTime, int currentIncome) {
        // Calculate income at current node u
        int nodeIncome = 0;
        if (aliceTime < bobTime[u]) {
            nodeIncome = amount[u];
        } else if (aliceTime == bobTime[u]) {
            nodeIncome = amount[u] / 2;
        }

        int newIncome = currentIncome + nodeIncome;

        int childrenCount = 0;
        for (int v : adj[u]) {
            if (v != p) {
                childrenCount++;
                dfs(v, u, aliceTime + 1, newIncome);
            }
        }

        if (childrenCount == 0) { // It's a leaf node
            maxIncome = Math.max(maxIncome, newIncome);
        }
    }
}
```
### Algorithm
*   **Build Adjacency List:** Represent the tree using an adjacency list for efficient neighbor lookups.
*   **Pre-compute Bob's Path and Timings:**
    1.  First, determine the parent of each node in the tree with respect to the root `0`. A BFS starting from `0` is suitable for this.
    2.  Create a `bobTime` array of size `n`, initialized to a large value (infinity). This will store the time it takes Bob to reach any node.
    3.  Trace Bob's path from his start node `bob` to `0` using the parent pointers. For each node `u` on this path at a distance `d` from `bob`, set `bobTime[u] = d`.
*   **Perform a Single DFS for Alice:**
    1.  Define a recursive DFS function, `dfs(node, parent, aliceTime, currentIncome)`, to explore paths from the root.
    2.  Initialize a global `maxIncome` variable to `Integer.MIN_VALUE`.
    3.  Start the traversal from the root: `dfs(0, -1, 0, 0)`.
*   **Inside the DFS:**
    1.  For the current `node`, calculate the income Alice gets. Compare her arrival time, `aliceTime`, with Bob's pre-computed time, `bobTime[node]`.
        *   If `aliceTime < bobTime[node]`, she gets `amount[node]`.
        *   If `aliceTime == bobTime[node]`, she gets `amount[node] / 2`.
        *   Otherwise, she gets `0`.
    2.  Add this income to the `currentIncome` for the path so far.
    3.  Check if the current `node` is a leaf. A node is a leaf if it has no children in the DFS traversal. If it is a leaf, update `maxIncome = max(maxIncome, currentIncome)`.
    4.  Recursively call the DFS for all unvisited neighbors (children) of the current `node`, incrementing `aliceTime` and passing the updated `currentIncome`.
*   **Return Result:** After the DFS completes, `maxIncome` holds the answer.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  int[] amount;
private
  int[] ts;
private
  int ans = Integer.MIN_VALUE;
public
  int mostProfitablePath(int[][] edges, int bob, int[] amount) {
    int n = edges.length + 1;
    g = new List[n];
    ts = new int[n];
    this.amount = amount;
    Arrays.setAll(g, k->new ArrayList<>());
    Arrays.fill(ts, n);
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    dfs1(bob, -1, 0);
    ts[bob] = 0;
    dfs2(0, -1, 0, 0);
    return ans;
  }
private
  boolean dfs1(int i, int fa, int t) {
    if (i == 0) {
      ts[i] = Math.min(ts[i], t);
      return true;
    }
    for (int j : g[i]) {
      if (j != fa && dfs1(j, i, t + 1)) {
        ts[j] = Math.min(ts[j], t + 1);
        return true;
      }
    }
    return false;
  }
private
  void dfs2(int i, int fa, int t, int v) {
    if (t == ts[i]) {
      v += amount[i] >> 1;
    } else if (t < ts[i]) {
      v += amount[i];
    }
    if (g[i].size() == 1 && g[i].get(0) == fa) {
      ans = Math.max(ans, v);
      return;
    }
    for (int j : g[i]) {
      if (j != fa) {
        dfs2(j, i, t + 1, v);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int mostProfitablePath(vector<vector<int>> &edges, int bob,
                         vector<int> &amount) {
    int n = edges.size() + 1;
    vector<vector<int>> g(n);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].emplace_back(b);
      g[b].emplace_back(a);
    }
    vector<int> ts(n, n);
    function<bool(int i, int fa, int t)> dfs1 = [&](int i, int fa,
                                                    int t) -> bool {
      if (i == 0) {
        ts[i] = t;
        return true;
      }
      for (int j : g[i]) {
        if (j != fa && dfs1(j, i, t + 1)) {
          ts[j] = min(ts[j], t + 1);
          return true;
        }
      }
      return false;
    };
    dfs1(bob, -1, 0);
    ts[bob] = 0;
    int ans = INT_MIN;
    function<void(int i, int fa, int t, int v)> dfs2 = [&](int i, int fa, int t,
                                                           int v) {
      if (t == ts[i])
        v += amount[i] >> 1;
      else if (t < ts[i])
        v += amount[i];
      if (g[i].size() == 1 && g[i][0] == fa) {
        ans = max(ans, v);
        return;
      }
      for (int j : g[i])
        if (j != fa)
          dfs2(j, i, t + 1, v);
    };
    dfs2(0, -1, 0, 0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int: def dfs1(i, fa, t): if i == 0: ts[i] = min(ts[i], t) return True for j in g[i]: if j != fa and dfs1(j, i, t + 1): ts[j] = min(ts[j], t + 1) return True return False def dfs2(i, fa, t, v): if t == ts[i]: v += amount[i] // 2 elif t < ts[i]: v += amount[i] nonlocal ans if len(g[i]) == 1 and g[i][0] == fa: ans = max(ans, v) return for j in g[i]: if j != fa: dfs2(j, i, t + 1, v) n = len(edges) + 1 g = defaultdict(list) ts = [n] * n for a, b in edges: g[a]. append(b) g[b]. append(a) dfs1(bob, - 1, 0) ts[bob] = 0 ans = - inf dfs2(0, - 1, 0, 0) return ans

```