3575. Maximum Good Subtree Score
Hard
50 Points
Array
Dynamic Programming
Bit Manipulation
Tree
Depth-First Search
Bitmask
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].
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.
The score of a good subset is the sum of the values of its nodes.
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.
Return the sum of all values in maxScore.
Since the answer may be large, return it modulo 109 + 7.
Examples
Example 1
Input: vals = [2,3], par = [-1,0]
Output: 8
Explanation:
Example 2
Input: vals = [1,5,2], par = [-1,0,0]
Output: 15
Explanation:
Example 3
Input: vals = [34,1,2], par = [-1,0,1]
Output: 42
Explanation:
Example 4
Input: vals = [3,22,5], par = [-1,0,1]
Output: 18
Explanation:
Constraints
1 <= n == vals.length <= 5001 <= vals[i] <= 109par.length == npar[0] == -10 <= par[i] < n for i in [1, n - 1]The input is generated such that the parent array par represents a valid tree.
3575. Maximum Good Subtree Score
Hard
50 Points
Array
Dynamic Programming
Bit Manipulation
Tree
Depth-First Search
Bitmask
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].
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.
The score of a good subset is the sum of the values of its nodes.
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.
Return the sum of all values in maxScore.
Since the answer may be large, return it modulo 109 + 7.
Examples
Example 1
Input: vals = [2,3], par = [-1,0]
Output: 8
Explanation:
Example 2
Input: vals = [1,5,2], par = [-1,0,0]
Output: 15
Explanation:
Example 3
Input: vals = [34,1,2], par = [-1,0,1]
Output: 42
Explanation:
Example 4
Input: vals = [3,22,5], par = [-1,0,1]
Output: 18
Explanation:
Constraints
1 <= n == vals.length <= 5001 <= vals[i] <= 109par.length == npar[0] == -10 <= par[i] < n for i in [1, n - 1]The input is generated such that the parent array par represents a valid tree.