Problem Statement & Gate-Sharing Mechanics

You are given an undirected tree with n nodes labeled 0 to n - 1, rooted at node 0, represented by a 2D array edges of length n - 1. At every node i, an even integer amount[i] specifies either the cost to open the gate (if negative) or the cash reward (if positive).

• At t = 0, Alice starts at node 0 and moves toward an arbitrary leaf node, while Bob starts at node bob and moves along the unique shortest path toward node 0.
• Alice arrives first (t_alice < t_bob): Alice pays the full cost or collects the full reward amount[u].
• Simultaneous arrival (t_alice == t_bob): Alice and Bob split the gate cost or reward equally, so Alice receives amount[u] / 2 (guaranteed integer because amount[u] is even).
• Bob arrives first (t_alice > t_bob): The gate is already open when Alice arrives; Alice's net delta at node u is 0.

Return the maximum net income Alice can achieve upon reaching any leaf node.

Example Walkthroughs & Tree Topologies

Example 1:
Tree Topology:
      0 (-2)
      |
      1 (+4)
     / \
  2(+2) 3 (-4) [Bob starts at node 3]
         |
        4 (+6)

Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
Output: 6
Timeline:
- t = 0: Alice at 0 (income = -2), Bob at 3 (opens gate 3).
- t = 1: Alice and Bob both reach node 1 simultaneously. They split +4 -> Alice gets +2 (net = 0).
- t = 2: Alice moves to node 3 (already opened by Bob at t = 0 -> +0); Bob reaches 0 and stops.
- t = 3: Alice reaches leaf node 4 and collects +6 (total net income = 6).

Example 2:
Input: edges = [[0,1]], bob = 1, amount = [-7280, 2350]
Output: -7280
Explanation: At t = 0, Alice opens gate 0 (-7280) and Bob opens gate 1. At t = 1, Alice reaches leaf 1 (already open -> +0).

Algorithmic Architecture: Decoupling Bob & Alice via Arrival Timestamps

Phase 1: Finding Bob's Unique Path to Root 0

Since a tree contains no cycles, there is exactly one simple path from bob to 0. A DFS starting at bob searches for 0 and records the step index bobTime[u] for every vertex u on that path (initializing all off-path vertices to -1 or ∞).

Phase 2: Maximizing Alice's Root-to-Leaf Path Sum

Next, we run a DFS from root 0 at depth time = 0. At each node u, we compute Alice's gate contribution by comparing time against bobTime[u], and recursively accumulate the maximum child subtree return value across all unvisited neighbors.

C++20 Implementation

#include <vector>
#include <climits>
#include <algorithm>

class Solution {
public:
    int mostProfitablePath(std::vector<std::vector<int>>& edges, int bob, std::vector<int>& amount) {
        int n = static_cast<int>(amount.size());
        std::vector<std::vector<int>> graph(n);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        std::vector<int> bobTime(n, -1);
        findBobPath(graph, bob, -1, 0, bobTime);

        return dfsAlice(graph, 0, -1, 0, bobTime, amount);
    }

private:
    bool findBobPath(const std::vector<std::vector<int>>& graph, int u, int parent, int time,
                     std::vector<int>& bobTime) {
        if (u == 0) {
            bobTime[u] = time;
            return true;
        }
        for (int v : graph[u]) {
            if (v != parent && findBobPath(graph, v, u, time + 1, bobTime)) {
                bobTime[u] = time;
                return true;
            }
        }
        return false;
    }

    int dfsAlice(const std::vector<std::vector<int>>& graph, int u, int parent, int time,
                 const std::vector<int>& bobTime, const std::vector<int>& amount) {
        int income = 0;
        if (bobTime[u] == -1 || time < bobTime[u]) {
            income = amount[u];
        } else if (time == bobTime[u]) {
            income = amount[u] / 2;
        }

        int maxChildProfit = INT_MIN;
        for (int v : graph[u]) {
            if (v != parent) {
                maxChildProfit = std::max(maxChildProfit, dfsAlice(graph, v, u, time + 1, bobTime, amount));
            }
        }

        return maxChildProfit == INT_MIN ? income : income + maxChildProfit;
    }
};

TypeScript Implementation

export function mostProfitablePath(edges: number[][], bob: number, amount: number[]): number {
  const n = amount.length;
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const bobTime = new Int32Array(n).fill(-1);

  function findBob(u: number, parent: number, time: number): boolean {
    if (u === 0) {
      bobTime[u] = time;
      return true;
    }
    for (const v of graph[u]) {
      if (v !== parent && findBob(v, u, time + 1)) {
        bobTime[u] = time;
        return true;
      }
    }
    return false;
  }

  findBob(bob, -1, 0);

  function dfsAlice(u: number, parent: number, time: number): number {
    let income = 0;
    if (bobTime[u] === -1 || time < bobTime[u]) {
      income = amount[u];
    } else if (time === bobTime[u]) {
      income = amount[u] / 2;
    }

    let maxChild = -Infinity;
    for (const v of graph[u]) {
      if (v !== parent) {
        const childProfit = dfsAlice(v, u, time + 1);
        if (childProfit > maxChild) maxChild = childProfit;
      }
    }

    return maxChild === -Infinity ? income : income + maxChild;
  }

  return dfsAlice(0, -1, 0);
}

Complexity & Systems Analysis

• Time Complexity: O(N). Building the adjacency list visits N - 1 edges, and both DFS passes traverse each vertex and tree edge at most once using parent-pointer pruning (avoiding separate boolean visited array resets).
• Auxiliary Space Complexity: O(N) for the adjacency list, bobTime lookup array, and recursion stack depth up to tree height O(H) ≤ O(N).