Choose Alice's Most Profitable Root-to-Leaf Route against Bob

### Problem The undirected tree `edges` is rooted at node 0. Alice starts at 0 and moves one edge per second along a route to a leaf. Bob starts at `bob` and moves one edge per second along the unique route to 0. Each stops on reaching their own destination, independently of the other. Gate `i` has an even signed value `amount[i]`: a negative value is a cost and a nonnegative value is a reward. The first visitor opens the gate and pays or receives that amount. Simultaneous visitors split it equally; later visitors pay and receive nothing. Both starting gates open at time zero. Return Alice's greatest possible net income over her choice of leaf. ```cpp class Solution { public: int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount); }; ``` ### Examples **Example 1:** ```text Input: edges = [[0,1],[0,2]], bob = 1, amount = [2,10,6] Output: 8 Explanation: Alice receives 2 at the root and 6 at leaf 2. Bob has already opened the gate at 1. ``` **Example 2:** ```text Input: edges = [[0,1],[1,2]], bob = 2, amount = [-2,4,8] Output: 0 Explanation: Alice pays 2 at node 0, receives half of 4 at node 1, then receives nothing at node 2 because Bob arrived first. ``` ### Constraints - `2 <= n <= 100000`; edges contains n-1 distinct valid undirected tree edges. - `1 <= bob < n`. - amount has n even integers in[-10000,10000]. ### Clarifying Questions - Can either player wait or change speed? No. - What happens on a simultaneous arrival at a negative gate? Each pays half the cost. - Must Alice reach a leaf even if income is negative? Yes. - Does one player stop the other by reaching their destination? No; stopping is independent. ```hint Check the boundary Check the starting gates at time zero and a gate reached simultaneously by both players. ```