2440. Create Components With Same Value Hard

1/**
2 * [2440] Create Components With Same Value
3 *
4 * There is an undirected tree with n nodes labeled from 0 to n - 1.
5 * You are given a 0-indexed integer array <font face="monospace">nums</font> of length n where nums[i] represents the value of the i^th node. You are also 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.
6 * You are allowed to delete some edges, splitting the tree into multiple connected components. Let the value of a component be the sum of all nums[i] for which node i is in the component.
7 * Return the maximum number of edges you can delete, such that every connected component in the tree has the same value.
8 *  
9 * <strong class="example">Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2022/08/26/diagramdrawio.png" style="width: 441px; height: 351px;" />
11 * Input: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] 
12 * Output: 2 
13 * Explanation: The above figure shows how we can delete the edges [0,1] and [3,4]. The created components are nodes [0], [1,2,3] and [4]. The sum of the values in each component equals 6. It can be proven that no better deletion exists, so the answer is 2.
14 * 
15 * <strong class="example">Example 2:
16 * 
17 * Input: nums = [2], edges = []
18 * Output: 0
19 * Explanation: There are no edges to be deleted.
20 * 
21 *  
22 * Constraints:
23 * 
24 * 	1 <= n <= 2 * 10^4
25 * 	nums.length == n
26 * 	1 <= nums[i] <= 50
27 * 	edges.length == n - 1
28 * 	edges[i].length == 2
29 * 	0 <= edges[i][0], edges[i][1] <= n - 1
30 * 	edges represents a valid tree.
31 * 
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/create-components-with-same-value/
36// discuss: https://leetcode.com/problems/create-components-with-same-value/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn component_value(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
42        0
43    }
44}
45
46// submission codes end
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_2440() {
54    }
55}
56