2925. Maximum Score After Applying Operations on a Tree Medium

1/**
2 * [2925] Maximum Score After Applying Operations on a Tree
3 *
4 * There is an undirected tree with n nodes labeled from 0 to n - 1, and 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 * You are also given a 0-indexed integer array values of length n, where values[i] is the value associated with the i^th node.
6 * You start with a score of 0. In one operation, you can:
7 * 
8 * 	Pick any node i.
9 * 	Add values[i] to your score.
10 * 	Set values[i] to 0.
11 * 
12 * A tree is healthy if the sum of values on the path from the root to any leaf node is different than zero.
13 * Return the maximum score you can obtain after performing these operations on the tree any number of times so that it remains healthy.
14 *  
15 * <strong class="example">Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2023/10/11/graph-13-1.png" style="width: 515px; height: 443px;" />
17 * Input: edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
18 * Output: 11
19 * Explanation: We can choose nodes 1, 2, 3, 4, and 5. The value of the root is non-zero. Hence, the sum of values on the path from the root to any leaf is different than zero. Therefore, the tree is healthy and the score is values[1] + values[2] + values[3] + values[4] + values[5] = 11.
20 * It can be shown that 11 is the maximum score obtainable after any number of operations on the tree.
21 * 
22 * <strong class="example">Example 2:
23 * <img alt="" src="https://assets.leetcode.com/uploads/2023/10/11/graph-14-2.png" style="width: 522px; height: 245px;" />
24 * Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
25 * Output: 40
26 * Explanation: We can choose nodes 0, 2, 3, and 4.
27 * - The sum of values on the path from 0 to 4 is equal to 10.
28 * - The sum of values on the path from 0 to 3 is equal to 10.
29 * - The sum of values on the path from 0 to 5 is equal to 3.
30 * - The sum of values on the path from 0 to 6 is equal to 5.
31 * Therefore, the tree is healthy and the score is values[0] + values[2] + values[3] + values[4] = 40.
32 * It can be shown that 40 is the maximum score obtainable after any number of operations on the tree.
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	2 <= n <= 2 * 10^4
38 * 	edges.length == n - 1
39 * 	edges[i].length == 2
40 * 	0 <= ai, bi < n
41 * 	values.length == n
42 * 	1 <= values[i] <= 10^9
43 * 	The input is generated such that edges represents a valid tree.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/maximum-score-after-applying-operations-on-a-tree/
49// discuss: https://leetcode.com/problems/maximum-score-after-applying-operations-on-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn maximum_score_after_operations(edges: Vec<Vec<i32>>, values: Vec<i32>) -> i64 {
55        
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_2925() {
67    }
68}
69