#603 · #2467 · Most Profitable Path in a Tree(树上最大得分和路径)

There is a tree of n nodes rooted at 0. Alice starts at 0 and Bob at bob; both move one edge per second toward node 0, and Bob cannot change direction. Alice earns amount[i] for a node she reaches first, amount[i]/2 if they arrive together, and nothing if Bob arrived first. Return Alice's maximum total income. Constraints: 2 <= n <= 10^5, 1 <= amount[i] <= 1000.