#2467

Most Profitable Path in a Tree

specialist · 615 · lc medium +29 · verified · 67.3% accepted · 1,402 likes · top 73%

⚑ Recursive DFS Traversal

Description

There is an undirected tree with n nodes labeled 0 to n - 1, rooted at node 0. Edges are given by a 2D array edges.

Alice starts at node 0 (Bob's starting node is given). Bob moves from his starting node toward node 0 along the unique path, advancing one node per turn. Alice simultaneously moves from node 0 to any leaf, also one node per turn.

Each node i has an amount amount[i] (can be negative). The first person to reach a node collects the full amount; if both arrive simultaneously, each collects half. Alice wants to maximize her collected total, while Bob moves optimally (with no regard for Alice's score).

Return Alice's maximum possible net income.

Example 1:

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:

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.

Code

1
2
3