Maximum Good Subtree Score

• For each node u from 0 to n-1:
  • Determine the set of all nodes in the subtree of u, let's call it S_u.
  • Generate all 2^|S_u| subsets of S_u.
  • For each subset, check if it is a "good" subset:
    • A subset is good if the combined set of digits from the values of all its nodes contains each digit from 0-9 at most once.
    • This means any node with a value containing repeated digits (e.g., 11, 232) cannot be in a good subset with any other node, and also that the digit sets of any two chosen nodes must be disjoint.
  • If a subset is good, calculate its score (the sum of values of its nodes).
  • Keep track of the maximum score found among all good subsets. This will be maxScore[u].
• After computing maxScore[u] for all u, sum them up to get the final answer.

The brute-force method involves a straightforward, yet computationally intensive, process for each node in the tree.

1. Tree Traversal and Subtree Identification: First, we need to represent the tree, for example, using an adjacency list built from the par array. Then, for every node u from 0 to n-1, we perform a traversal (like DFS or BFS) starting from u to find all nodes that are part of its subtree.

2. Subset Generation and Validation: Once we have the list of nodes in u's subtree, we generate all possible subsets. For each subset, we must check its validity:

   • We maintain a bitmask, totalDigitsMask, to keep track of the digits used so far.
   • For each node in the current subset, we compute the digit mask of its value. A number with repeated digits (e.g., 33, 121) is invalid on its own.
   • If a node's value is valid, we check if its digit mask has any bits in common with totalDigitsMask. If it does, there's a digit conflict, and the subset is not good.
   • If there are no conflicts, we update totalDigitsMask by OR-ing it with the node's digit mask.

3. Score Calculation: If a subset is validated as good, we calculate its score by summing the vals of all its nodes. We keep track of the maximum score seen for the current subtree u.

4. Final Summation: This process is repeated for every node in the tree. The final result is the sum of all calculated maxScore values, taken modulo 10^9 + 7.

Due to the 2^k complexity of generating subsets for a subtree of size k (where k can be up to n), this approach is not feasible for the given constraints.

• Preprocessing:
  • Convert the parent array par into an adjacency list representation of the tree.
  • For each node i, compute a bitmask representing the unique digits in vals[i]. If vals[i] contains any repeated digits (e.g., 112), mark it as invalid (e.g., with a mask of -1).
• DFS with Dynamic Programming:
  • Use a post-order traversal (DFS) to solve the problem from leaves up to the root.
  • For each node u, we compute a DP table, dp[u], which is an array of size 1024. dp[u][mask] stores the maximum score of a good subset in u's subtree that has a combined digit mask of mask.
  • The dfs(u) function returns this DP table for its subtree.
• Base Case (in DFS):
  • For a node u, initialize its DP table dp_u. Set dp_u[0] = 0 (empty set). If vals[u] has a valid digit mask m_u, set dp_u[m_u] = vals[u].
• Recursive Step (in DFS):
  • For each child c of u, recursively call dfs(c) to get its DP table dp_c.
  • Merge dp_c into dp_u. The merge operation combines the results from the two subproblems. A new table new_dp is created where new_dp[m] is the maximum score for a combined mask m. This is calculated as max(dp_u[m1] + dp_c[m2]) over all disjoint m1, m2 such that m1 | m2 = m.
  • This merge can be done in O(3^10) time by iterating through all masks m and their submasks m1.
• Result Calculation:
  • After all children of u have been processed, the final dp_u table for the subtree at u is ready.
  • maxScore[u] is the maximum value in the dp_u table.
  • Add maxScore[u] to a running total sum, modulo 10^9 + 7.
• Final Answer: The final answer is the total sum after the DFS traversal completes.

This approach leverages dynamic programming on trees to efficiently solve the problem.

First, we preprocess the input. We build an adjacency list for the tree. For each node's value, we compute a 10-bit mask representing its unique digits. If a value has repeated digits (e.g., 55), it's considered invalid and cannot be combined with other nodes.

We use a DFS function, dfs(u, parent), which returns a DP table for the subtree rooted at u. This table is an array of long of size 1024, where dp[mask] stores the maximum score for a good subset using digits specified by mask.

Inside dfs(u, parent):

1. Initialization: We create a DP table dp_u for node u. We initialize dp_u[0] = 0 (representing an empty subset with score 0). If vals[u] has a valid digit mask m_u, we set dp_u[m_u] = vals[u]. All other entries are initialized to a sentinel value like -1.
2. Recursion and Merging: We iterate through each child c of u. We make a recursive call dfs(c, u) to get the DP table dp_c for the child's subtree. Then, we merge dp_c into dp_u. The merge function creates a new DP table by combining subsets from u's part and c's part. For each possible resulting mask m, we find the best combination of a submask m1 from dp_u and a submask m2 from dp_c such that m1 and m2 are disjoint and m1 | m2 = m. The new score would be dp_u[m1] + dp_c[m2]. This is done for all possible resulting masks.
3. Finalizing maxScore[u]: After all children are merged, dp_u is final. maxScore[u] is the maximum value in this table. We add this to a global sum.
4. The function returns the final dp_u table.

Here is a code snippet for the merge logic:

1private long[] merge(long[] dp1, long[] dp2) {2    long[] newDp = new long[1024];3    Arrays.fill(newDp, -1L);4 5    for (int mask = 0; mask < 1024; mask++) {6        // Iterate over all submasks of the current mask.7        // This loop structure efficiently visits all submasks.8        for (int submask = mask; ; submask = (submask - 1) & mask) {9            int otherSubmask = mask ^ submask;10            if (dp1[submask] != -1 && dp2[otherSubmask] != -1) {11                long currentScore = dp1[submask] + dp2[otherSubmask];12                if (newDp[mask] < currentScore) {13                    newDp[mask] = currentScore;14                }15            }16            if (submask == 0) {17                break; // End loop after processing the empty submask.18            }19        }20    }21    return newDp;22}

The main function initiates the DFS from the root (node 0) and returns the accumulated total sum.