Most Profitable Path in a Tree

Separate the two paths

Root the tree at node 0. First find the unique path from Bob's starting node to the root and record bobTime[node] only for nodes on that path. Then DFS Alice from the root, carrying her time and running profit. At each node, take the full amount if Alice arrives first, half if arrival times tie, and zero if Bob arrived earlier.

Only update the answer at a root-to-leaf endpoint, because Alice must finish at a leaf. The key invariant is that Bob's arrival time is fixed by his unique path, while Alice explores every legal root-to-leaf route. Building the graph, finding Bob's path, and Alice's DFS are all O(n) time and O(n) space for adjacency, recursion/stack, and arrival times. Test a one-node tree, Bob at the root, a meeting exactly midway, negative amounts, and a branch Bob never visits. Avoid mutating shared amounts across sibling DFS branches unless you restore them.