3575. Maximum Good Subtree Score Hard

1/**
2 * [3575] Maximum Good Subtree Score
3 *
4 * You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. Each node i has an integer value vals[i], and its parent is given by par[i].
5 * A subset of nodes within the subtree of a node is called good if every digit from 0 to 9 appears at most once in the decimal representation of the values of the selected nodes.
6 * The score of a good subset is the sum of the values of its nodes.
7 * Define an array maxScore of length n, where maxScore[u] represents the maximum possible sum of values of a good subset of nodes that belong to the subtree rooted at node u, including u itself and all its descendants.
8 * Return the sum of all values in maxScore.
9 * Since the answer may be large, return it modulo 10^9 + 7.
10 *  
11 * <strong class="example">Example 1:
12 * <div class="example-block">
13 * Input: <span class="example-io">vals = [2,3], par = [-1,0]</span>
14 * Output: <span class="example-io">8</span>
15 * Explanation:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/29/screenshot-2025-04-29-at-150754.png" style="height: 84px; width: 180px;" />
17 * 
18 * 	The subtree rooted at node 0 includes nodes {0, 1}. The subset {2, 3} is good as the digits 2 and 3 appear only once. The score of this subset is 2 + 3 = 5.
19 * 	The subtree rooted at node 1 includes only node {1}. The subset {3} is good. The score of this subset is 3.
20 * 	The maxScore array is [5, 3], and the sum of all values in maxScore is 5 + 3 = 8. Thus, the answer is 8.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">vals = [1,5,2], par = [-1,0,0]</span>
25 * Output: <span class="example-io">15</span>
26 * Explanation:
27 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/29/screenshot-2025-04-29-at-151408.png" style="width: 205px; height: 140px;" />
28 * 
29 * 	The subtree rooted at node 0 includes nodes {0, 1, 2}. The subset {1, 5, 2} is good as the digits 1, 5 and 2 appear only once. The score of this subset is 1 + 5 + 2 = 8.
30 * 	The subtree rooted at node 1 includes only node {1}. The subset {5} is good. The score of this subset is 5.
31 * 	The subtree rooted at node 2 includes only node {2}. The subset {2} is good. The score of this subset is 2.
32 * 	The maxScore array is [8, 5, 2], and the sum of all values in maxScore is 8 + 5 + 2 = 15. Thus, the answer is 15.
33 * </div>
34 * <strong class="example">Example 3:
35 * <div class="example-block">
36 * Input: <span class="example-io">vals = [34,1,2], par = [-1,0,1]</span>
37 * Output: <span class="example-io">42</span>
38 * Explanation:
39 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/29/screenshot-2025-04-29-at-151747.png" style="height: 80px; width: 256px;" />
40 * 
41 * 	The subtree rooted at node 0 includes nodes {0, 1, 2}. The subset {34, 1, 2} is good as the digits 3, 4, 1 and 2 appear only once. The score of this subset is 34 + 1 + 2 = 37.
42 * 	The subtree rooted at node 1 includes node {1, 2}. The subset {1, 2} is good as the digits 1 and 2 appear only once. The score of this subset is 1 + 2 = 3.
43 * 	The subtree rooted at node 2 includes only node {2}. The subset {2} is good. The score of this subset is 2.
44 * 	The maxScore array is [37, 3, 2], and the sum of all values in maxScore is 37 + 3 + 2 = 42. Thus, the answer is 42.
45 * </div>
46 * <strong class="example">Example 4:
47 * <div class="example-block">
48 * Input: <span class="example-io">vals = [3,22,5], par = [-1,0,1]</span>
49 * Output: <span class="example-io">18</span>
50 * Explanation:
51 * 
52 * 	The subtree rooted at node 0 includes nodes {0, 1, 2}. The subset {3, 22, 5} is not good, as digit 2 appears twice. Therefore, the subset {3, 5} is valid. The score of this subset is 3 + 5 = 8.
53 * 	The subtree rooted at node 1 includes nodes {1, 2}. The subset {22, 5} is not good, as digit 2 appears twice. Therefore, the subset {5} is valid. The score of this subset is 5.
54 * 	The subtree rooted at node 2 includes {2}. The subset {5} is good. The score of this subset is 5.
55 * 	The maxScore array is [8, 5, 5], and the sum of all values in maxScore is 8 + 5 + 5 = 18. Thus, the answer is 18.
56 * 
57 * 
58 * </div>
59 *  
60 * Constraints:
61 * 
62 * 	1 <= n == vals.length <= 500
63 * 	1 <= vals[i] <= 10^9
64 * 	par.length == n
65 * 	par[0] == -1
66 * 	0 <= par[i] < n for i in [1, n - 1]
67 * 	The input is generated such that the parent array par represents a valid tree.
68 * 
69 */
70pub struct Solution {}
71
72// problem: https://leetcode.com/problems/maximum-good-subtree-score/
73// discuss: https://leetcode.com/problems/maximum-good-subtree-score/discuss/?currentPage=1&orderBy=most_votes&query=
74
75// submission codes start here
76
77impl Solution {
78    pub fn good_subtree_sum(vals: Vec<i32>, par: Vec<i32>) -> i32 {
79        0
80    }
81}
82
83// submission codes end
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn test_3575() {
91    }
92}
93