# Maximum Good Subtree Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-good-subtree-score)
Canonical: https://scaleengineer.com/dsa/problems/maximum-good-subtree-score
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree
---
## Problem
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`.

**Example 1:**

**Input:** vals = \[2,3\], par = \[-1,0\]

**Output:** 8

**Explanation:**

![](https://assets.glich.co/dsa/maximum-good-subtree-score/image0.png)

* The subtree rooted at node 0 includes nodes `{0, 1}`. The subset `{2, 3}` isgood as the digits 2 and 3 appear only once. The score of this subset is `2 + 3 = 5`.
* The subtree rooted at node 1 includes only node `{1}`. The subset `{3}` isgood. The score of this subset is 3.
* The `maxScore` array is `[5, 3]`, and the sum of all values in `maxScore` is `5 + 3 = 8`. Thus, the answer is 8.

**Example 2:**

**Input:** vals = \[1,5,2\], par = \[-1,0,0\]

**Output:** 15

**Explanation:**

**![](https://assets.glich.co/dsa/maximum-good-subtree-score/image1.png)**

* The subtree rooted at node 0 includes nodes `{0, 1, 2}`. The subset `{1, 5, 2}` isgood as the digits 1, 5 and 2 appear only once. The score of this subset is `1 + 5 + 2 = 8`.
* The subtree rooted at node 1 includes only node `{1}`. The subset `{5}` isgood. The score of this subset is 5.
* The subtree rooted at node 2 includes only node `{2}`. The subset `{2}` isgood. The score of this subset is 2.
* 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.

**Example 3:**

**Input:** vals = \[34,1,2\], par = \[-1,0,1\]

**Output:** 42

**Explanation:**

![](https://assets.glich.co/dsa/maximum-good-subtree-score/image2.png)

* The subtree rooted at node 0 includes nodes `{0, 1, 2}`. The subset `{34, 1, 2}` isgood as the digits 3, 4, 1 and 2 appear only once. The score of this subset is `34 + 1 + 2 = 37`.
* The subtree rooted at node 1 includes node `{1, 2}`. The subset `{1, 2}` isgood as the digits 1 and 2 appear only once. The score of this subset is `1 + 2 = 3`.
* The subtree rooted at node 2 includes only node `{2}`. The subset `{2}` isgood. The score of this subset is 2.
* 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.

**Example 4:**

**Input:** vals = \[3,22,5\], par = \[-1,0,1\]

**Output:** 18

**Explanation:**

* The subtree rooted at node 0 includes nodes `{0, 1, 2}`. The subset `{3, 22, 5}` isnot good, as digit 2 appears twice. Therefore, the subset `{3, 5}` is valid. The score of this subset is `3 + 5 = 8`.
* The subtree rooted at node 1 includes nodes `{1, 2}`. The subset `{22, 5}` isnot good, as digit 2 appears twice. Therefore, the subset `{5}` is valid. The score of this subset is 5.
* The subtree rooted at node 2 includes `{2}`. The subset `{5}` isgood. The score of this subset is 5.
* 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.

**Constraints:**

* `1 <= n == vals.length <= 500`
* `1 <= vals[i] <= 109`
* `par.length == n`
* `par[0] == -1`
* `0 <= par[i] < n` for `i` in `[1, n - 1]`
* The input is generated such that the parent array `par` represents a valid tree.

# Approaches
## Brute Force by Enumerating Subsets
This approach directly follows the problem definition. For each node `u` in the tree, we first identify all nodes in its subtree. Then, we exhaustively generate every possible subset of these nodes. For each subset, we verify if it meets the "good" criteria (no repeated digits across all selected node values). If it is good, we compute its score. The maximum score found among all good subsets for the subtree of `u` is `maxScore[u]`. Finally, we sum up `maxScore[u]` for all nodes `u`.
**Time:** O(N * 2^N * N * log(V)), where N is the number of nodes and V is the maximum value in `vals`. For each of the N nodes, we might have a subtree of size up to N. Generating and checking all `2^N` subsets takes `O(2^N * N * log(V))`. This is prohibitively slow. · **Space:** O(N) to store the nodes of a subtree during processing and for the recursion stack.
**Pros:** Simple to conceptualize and implement.; Correctly solves the problem for very small inputs.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will not pass the time limits for the given constraints (`n` up to 500).
### Explanation
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.
### Algorithm
- 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.

## Dynamic Programming on Tree
A more efficient solution uses dynamic programming on the tree. We can perform a post-order traversal (DFS) from the root. For each node `u`, we compute a DP table that maps each possible digit mask (represented as a 10-bit integer) to the maximum score achievable for a good subset with that exact digit mask within `u`'s subtree.

The DP state for a node `u` is an array `dp_u` of size 1024, where `dp_u[mask]` is the max score. When processing a node `u`, we first initialize its DP table based on its own value. Then, for each child `c`, we recursively compute its DP table `dp_c` and merge it into `dp_u`. The merge operation combines scores from `u`'s currently processed subtree part and the child's subtree, considering all valid disjoint digit mask combinations. This merge step is akin to a subset convolution and can be performed in `O(3^10)` time. After processing all children, `maxScore[u]` is the maximum value in `dp_u`. The total answer is the sum of all `maxScore` values.
**Time:** O(N * 3^10). The DFS visits each of the N nodes once. At each node, it merges results from its children. A merge operation takes O(3^10) time because for each of the `2^10` possible final masks, we iterate through all its submasks. The total number of (mask, submask) pairs across all masks is `3^10`. · **Space:** O(N * 2^10) in the worst-case scenario of a skewed tree (like a path), where the recursion depth is N. Each recursive call stores a DP table of size 1024.
**Pros:** Efficient enough to solve the problem within the given constraints.; Systematically builds the solution from subproblems, which is a powerful technique.
**Cons:** The implementation can be complex, especially the merge step.; The time complexity has a large constant factor (`3^10`), but it's manageable for the given constraints.
### Explanation
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:
```java
private long[] merge(long[] dp1, long[] dp2) {
    long[] newDp = new long[1024];
    Arrays.fill(newDp, -1L);

    for (int mask = 0; mask < 1024; mask++) {
        // Iterate over all submasks of the current mask.
        // This loop structure efficiently visits all submasks.
        for (int submask = mask; ; submask = (submask - 1) & mask) {
            int otherSubmask = mask ^ submask;
            if (dp1[submask] != -1 && dp2[otherSubmask] != -1) {
                long currentScore = dp1[submask] + dp2[otherSubmask];
                if (newDp[mask] < currentScore) {
                    newDp[mask] = currentScore;
                }
            }
            if (submask == 0) {
                break; // End loop after processing the empty submask.
            }
        }
    }
    return newDp;
}
```
The main function initiates the DFS from the root (node 0) and returns the accumulated total sum.
### Algorithm
- **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.