2467. Most Profitable Path in a Tree Medium

1/**
2 * [2467] Most Profitable Path in a Tree
3 *
4 * There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
5 * At every node i, there is a gate. You are also given an array of even integers amount, where amount[i] represents:
6 * 
7 * 	the price needed to open the gate at node i, if amount[i] is negative, or,
8 * 	the cash reward obtained on opening the gate at node i, otherwise.
9 * 
10 * The game goes on as follows:
11 * 
12 * 	Initially, Alice is at node 0 and Bob is at node bob.
13 * 	At every second, Alice and Bob each move to an adjacent node. Alice moves towards some leaf node, while Bob moves towards node 0.
14 * 	For every node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:
15 * 	
16 * 		If the gate is already open, no price will be required, nor will there be any cash reward.
17 * 		If Alice and Bob reach the node simultaneously, they share the price/reward for opening the gate there. In other words, if the price to open the gate is c, then both Alice and Bob pay c / 2 each. Similarly, if the reward at the gate is c, both of them receive c / 2 each.
18 * 	
19 * 	
20 * 	If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node 0, he stops moving. Note that these events are independent of each other.
21 * 
22 * Return the maximum net income Alice can have if she travels towards the optimal leaf node.
23 *  
24 * <strong class="example">Example 1:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/29/eg1.png" style="width: 275px; height: 275px;" />
26 * Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
27 * Output: 6
28 * Explanation: 
29 * The above diagram represents the given tree. The game goes as follows:
30 * - Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes.
31 *   Alice's net income is now -2.
32 * - Both Alice and Bob move to node 1. 
33 *   Since they reach here simultaneously, they open the gate together and share the reward.
34 *   Alice's net income becomes -2 + (4 / 2) = 0.
35 * - Alice moves on to node 3. Since Bob already opened its gate, Alice's income remains unchanged.
36 *   Bob moves on to node 0, and stops moving.
37 * - Alice moves on to node 4 and opens the gate there. Her net income becomes 0 + 6 = 6.
38 * Now, neither Alice nor Bob can make any further moves, and the game ends.
39 * It is not possible for Alice to get a higher net income.
40 * 
41 * <strong class="example">Example 2:
42 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/29/eg2.png" style="width: 250px; height: 78px;" />
43 * Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]
44 * Output: -7280
45 * Explanation: 
46 * Alice follows the path 0->1 whereas Bob follows the path 1->0.
47 * Thus, Alice opens the gate at node 0 only. Hence, her net income is -7280. 
48 * 
49 *  
50 * Constraints:
51 * 
52 * 	2 <= n <= 10^5
53 * 	edges.length == n - 1
54 * 	edges[i].length == 2
55 * 	0 <= ai, bi < n
56 * 	ai != bi
57 * 	edges represents a valid tree.
58 * 	1 <= bob < n
59 * 	amount.length == n
60 * 	amount[i] is an even integer in the range [-10^4, 10^4].
61 * 
62 */
63pub struct Solution {}
64
65// problem: https://leetcode.com/problems/most-profitable-path-in-a-tree/
66// discuss: https://leetcode.com/problems/most-profitable-path-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
67
68// submission codes start here
69
70impl Solution {
71    pub fn most_profitable_path(edges: Vec<Vec<i32>>, bob: i32, amount: Vec<i32>) -> i32 {
72        0
73    }
74}
75
76// submission codes end
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_2467() {
84    }
85}
86