An undirected tree is rooted at node 0. Its nodes are labeled from 0 to n - 1, and edges lists its connections. Each node has a gate worth amount[i]: a positive amount is a reward, while a negative amount is a cost. Every amount is even.
Alice starts at node 0 and chooses a path to a leaf. Bob starts at node bob and follows the unique path toward node 0. Both open their starting gates at time 0 and move one edge each second. Alice stops at her chosen leaf; Bob stops at node 0.
The first person to reach a gate receives its reward or pays its cost. If they arrive simultaneously, each receives or pays half. A gate that has already been opened has no further effect.
Return the maximum net income Alice can earn by choosing her leaf. She must finish at a leaf even when every available path loses money.
Diagram nodes show node index:amount.
Example 1:
Input: edges = [[0,1],[1,2]]
bob = 2
amount = [4,6,8]
Output: 7Explanation: Alice opens node 0 for 4. At second 1, Alice and Bob both reach node 1 and split its reward, so Alice gains 3. Bob already opened node 2 before Alice arrives. Her total income is 4 + 3 = 7.
Example 2:
Input: edges = [[0,1],[0,2]]
bob = 1
amount = [-4,20,6]
Output: 2Explanation: Alice starts by paying 4 at node 0. Choosing leaf 2 earns her 6, giving a net income of 2. Choosing leaf 1 would earn nothing there because Bob opened it at time 0, leaving Alice with -4.
Example 3:
Input: edges = [[0,1],[1,2]]
bob = 2
amount = [-6,-4,-8]
Output: -8Explanation: Alice pays 6 at node 0 and half of the cost 4 at node 1, where she meets Bob. Node 2 is already open when she arrives. She must reach the leaf, so the maximum net income is -6 - 2 = -8.
Constraints:
2 <= n <= 100000edges.length == n - 1- Each edge contains two distinct integer labels between
0andn - 1. - The edges form a connected, undirected tree.
1 <= bob < namount.length == n- Every
amount[i]is even and lies between-10000and10000.