LeetCode Problem 3575

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Tree, Depth-First Search, Bitmask

Solution

LeetCode 3575 - Maximum Good Subtree Score

Problem Understanding

We are given a rooted tree with n nodes. Node 0 is the root, and the tree structure is described by the parent array par, where par[i] is the parent of node i.

Each node contains an integer value vals[i].

For every node u, we consider the entire subtree rooted at u, meaning u itself and all of its descendants.

Inside that subtree, we may choose any subset of nodes. A subset is considered good if, after writing down the decimal representation of all selected node values, every digit from 0 to 9 appears at most once overall.

For example:

• {12, 34} is good because digits {1,2,3,4} are all distinct.
• {12, 23} is not good because digit 2 appears twice.
• {22} is not good because digit 2 appears twice inside the same number.

The score of a good subset is simply the sum of the selected node values.

For each node u, we want:

maxScore[u] = maximum score of any good subset inside subtree(u)

Finally, we return:

sum(maxScore[u] for all nodes u) mod (10^9 + 7)

What the Constraints Tell Us

The important constraints are:

• n ≤ 500
• vals[i] ≤ 10^9

A value up to 10^9 contains at most 10 decimal digits.

The condition only concerns digits 0 through 9, which means there are only:

2^10 = 1024

possible digit-usage states.

This is the key observation. Although the tree may contain 500 nodes, the digit universe is extremely small. Whenever a problem involves tracking usage of only 10 items, a bitmask DP is usually appropriate.

Important Edge Cases

A few cases are particularly important:

• A number such as 22 is invalid by itself because digit 2 appears twice inside the same value.
• Different nodes may contain overlapping digits, preventing them from being chosen together.
• A subtree may have no valid node combinations except the empty subset.
• The optimal subset does not necessarily include the subtree root.
• Deep trees and highly branching trees must both be handled efficiently.

Approaches

Brute Force

For a node u, suppose its subtree contains k nodes.

A brute-force solution would enumerate all 2^k subsets, check whether each subset is good, compute its score, and take the maximum.

Repeating this for every node would be astronomically expensive.

Even for a subtree of size 30:

2^30 ≈ 1 billion

which is already impossible.

Therefore brute force is completely infeasible.

Key Observation

The goodness condition depends only on which digits have already been used.

There are only ten possible digits:

0,1,2,3,4,5,6,7,8,9

so we can represent used digits with a 10-bit mask.

For every node value:

• Compute the set of digits it uses.
• If a digit appears twice inside the value, mark the value as invalid.
• Otherwise store its digit mask.

Now the problem becomes a tree knapsack DP.

For each subtree we maintain:

dp[mask] = maximum score obtainable
           using exactly the digit set mask

When combining child subtrees, we merge masks similarly to a knapsack merge:

mask1 & mask2 == 0

must hold because digits cannot overlap.

The digit universe has size only 1024, making this DP practical.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential, O(n · 2^n) or worse	O(n)	Enumerates subsets of subtrees
Optimal	O(n · 1024²)	O(n · 1024)	Tree DP over digit masks

Algorithm Walkthrough

Step 1: Build the Tree

Construct the adjacency list from the parent array.

For every node:

children[parent].append(child)

This allows DFS traversal of each subtree.

Step 2: Compute Digit Masks

For every value:

1. Extract its decimal digits.
2. Build a bitmask representing used digits.
3. If any digit appears twice inside the same number, mark the value as invalid.

Examples:

34 -> mask(3,4)

105 -> mask(1,0,5)

22 -> invalid

An invalid number can never appear in a good subset.

Step 3: Define the DP State

For a subtree rooted at node u:

dp[mask]

stores the maximum score achievable inside that subtree whose used digits are exactly mask.

Initially:

dp[0] = 0

representing the empty subset.

Step 4: Merge Child Subtrees

Process children one by one.

Suppose:

current DP = dp
child DP = child_dp

For every pair of masks:

m1 from dp
m2 from child_dp

If:

(m1 & m2) == 0

then their digit sets do not overlap.

We may combine them:

new_mask = m1 | m2

new_dp[new_mask]
    = max(new_dp[new_mask],
          dp[m1] + child_dp[m2])

This is identical to a knapsack merge over bitmasks.

Step 5: Add the Current Node

After all children are merged, consider selecting node u.

If the node's value has a valid digit mask node_mask, then for every existing state:

(mask & node_mask) == 0

allows adding the node.

We create:

mask | node_mask

with score increased by vals[u].

Step 6: Compute maxScore[u]

The best good subset inside the subtree is simply:

max(dp.values())

Store this value as maxScore[u].

Step 7: Accumulate the Answer

During DFS, add each node's maximum score into the global answer.

Finally return:

answer mod (10^9 + 7)

Why it Works

The DP invariant is:

After processing a subtree, dp[mask] equals the maximum score obtainable from a good subset whose used digits are exactly mask.

The empty subset establishes the base case.

When merging child subtrees, we only combine masks with no common digit, preserving the good-subset property.

When adding the current node, we again require disjoint digit sets, ensuring no digit appears more than once.

Every valid subset corresponds to exactly one resulting mask, and every DP transition represents a valid subset construction. Therefore the maximum value stored among all masks is precisely the optimal score for that subtree.

Python Solution

from typing import List

class Solution:
    def goodSubtreeSum(self, vals: List[int], par: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(vals)

        children = [[] for _ in range(n)]
        for i in range(1, n):
            children[par[i]].append(i)

        def get_mask(x: int) -> int:
            mask = 0
            while x > 0:
                d = x % 10
                if (mask >> d) & 1:
                    return -1
                mask |= 1 << d
                x //= 10
            return mask

        digit_masks = [get_mask(v) for v in vals]

        answer = 0

        def dfs(u: int):
            nonlocal answer

            dp = {0: 0}

            for v in children[u]:
                child_dp = dfs(v)

                new_dp = {}

                for m1, s1 in dp.items():
                    for m2, s2 in child_dp.items():
                        if m1 & m2:
                            continue

                        nm = m1 | m2
                        cand = s1 + s2

                        if cand > new_dp.get(nm, -1):
                            new_dp[nm] = cand

                dp = new_dp

            node_mask = digit_masks[u]

            if node_mask != -1:
                updated = dict(dp)

                for mask, score in dp.items():
                    if mask & node_mask:
                        continue

                    nm = mask | node_mask
                    updated[nm] = max(
                        updated.get(nm, -1),
                        score + vals[u]
                    )

                dp = updated

            best = max(dp.values())
            answer += best

            return dp

        dfs(0)
        return answer % MOD

Implementation Explanation

The tree is first built from the parent array so that DFS can process subtrees naturally.

The helper function get_mask() converts a value into its digit bitmask. If a digit appears twice inside the same number, it returns -1, indicating that the node can never be selected.

The DFS returns a dictionary:

mask -> maximum score

for the entire subtree.

Each child subtree is merged into the current DP using a bitmask knapsack merge. Only disjoint masks may be combined.

After all children are processed, the current node is optionally added. This produces additional states whose digit masks remain valid.

The maximum score among all masks becomes maxScore[u], and it is accumulated into the global answer.

Go Solution

func goodSubtreeSum(vals []int, par []int) int {
	const MOD int = 1000000007

	n := len(vals)

	children := make([][]int, n)
	for i := 1; i < n; i++ {
		children[par[i]] = append(children[par[i]], i)
	}

	getMask := func(x int) int {
		mask := 0
		for x > 0 {
			d := x % 10
			if (mask>>d)&1 == 1 {
				return -1
			}
			mask |= 1 << d
			x /= 10
		}
		return mask
	}

	digitMasks := make([]int, n)
	for i := 0; i < n; i++ {
		digitMasks[i] = getMask(vals[i])
	}

	answer := 0

	var dfs func(int) map[int]int
	dfs = func(u int) map[int]int {
		dp := map[int]int{0: 0}

		for _, v := range children[u] {
			childDP := dfs(v)

			newDP := make(map[int]int)

			for m1, s1 := range dp {
				for m2, s2 := range childDP {
					if (m1 & m2) != 0 {
						continue
					}

					nm := m1 | m2
					cand := s1 + s2

					if cur, ok := newDP[nm]; !ok || cand > cur {
						newDP[nm] = cand
					}
				}
			}

			dp = newDP
		}

		nodeMask := digitMasks[u]

		if nodeMask != -1 {
			updated := make(map[int]int)

			for k, v := range dp {
				updated[k] = v
			}

			for mask, score := range dp {
				if (mask & nodeMask) != 0 {
					continue
				}

				nm := mask | nodeMask
				cand := score + vals[u]

				if cur, ok := updated[nm]; !ok || cand > cur {
					updated[nm] = cand
				}
			}

			dp = updated
		}

		best := 0
		for _, v := range dp {
			if v > best {
				best = v
			}
		}

		answer += best
		return dp
	}

	dfs(0)
	return answer % MOD
}

Go-Specific Notes

The Go version mirrors the Python solution almost exactly.

A map[int]int is used for sparse DP storage. This avoids allocating arrays of size 1024 for every subtree and keeps the implementation straightforward.

Since the total answer can grow beyond individual node values, accumulation is performed using Go integers and reduced modulo 10^9 + 7 at the end.

Worked Examples

Example 1

vals = [2,3]
par  = [-1,0]

Tree:

0
└──1

Digit masks:

Node	Value	Mask
0	2	0000000100
1	3	0000001000

Node 1

Initial:

Mask	Score
0	0

Add node 1:

Mask	Score
0	0
{3}	3

Best:

maxScore[1] = 3

Node 0

Merge child DP:

Mask	Score
0	0
{3}	3

Add value 2:

Mask	Score
0	0
{2}	2
{3}	3
{2,3}	5

Best:

maxScore[0] = 5

Final:

5 + 3 = 8

Example 2

vals = [1,5,2]
par = [-1,0,0]

Masks:

1 -> {1}
5 -> {5}
2 -> {2}

All masks are disjoint.

Subtree scores:

Node	Best Score
1	5
2	2
0	1 + 5 + 2 = 8

Answer:

8 + 5 + 2 = 15

Example 3

vals = [34,1,2]
par = [-1,0,1]

Masks:

34 -> {3,4}
1  -> {1}
2  -> {2}

All masks are compatible.

Node	Best Score
2	2
1	3
0	37

Answer:

37 + 3 + 2 = 42

Example 4

vals = [3,22,5]
par = [-1,0,1]

Mask of 22:

invalid

Node 1 cannot be selected.

Subtree DP at node 1 only uses child node 5.

Node	Best Score
2	5
1	5
0	8

Answer:

8 + 5 + 5 = 18

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n · 1024²)	Every merge considers pairs of digit masks
Space	O(n · 1024)	DP states across recursion

The digit universe contains only ten digits, so there are at most 2^10 = 1024 masks. During subtree merges we may compare pairs of masks, leading to a worst-case 1024² merge cost. Since there are n ≤ 500 nodes, this remains practical.

Test Cases

sol = Solution()

assert sol.goodSubtreeSum([2, 3], [-1, 0]) == 8          # example 1
assert sol.goodSubtreeSum([1, 5, 2], [-1, 0, 0]) == 15  # example 2
assert sol.goodSubtreeSum([34, 1, 2], [-1, 0, 1]) == 42 # example 3
assert sol.goodSubtreeSum([3, 22, 5], [-1, 0, 1]) == 18 # example 4

assert sol.goodSubtreeSum([7], [-1]) == 7               # single node

assert sol.goodSubtreeSum([11], [-1]) == 0              # invalid value alone

assert sol.goodSubtreeSum([12, 34], [-1, 0]) == 58      # fully compatible

assert sol.goodSubtreeSum([12, 23], [-1, 0]) == 35      # overlapping digit

assert sol.goodSubtreeSum([22, 33], [-1, 0]) == 0       # both invalid

assert sol.goodSubtreeSum([1, 2, 3, 4], [-1, 0, 1, 2]) == 30
# chain tree with all digits distinct

assert sol.goodSubtreeSum([98, 76, 54, 32, 10],
                          [-1, 0, 1, 2, 3]) == 950
# every node compatible with every descendant

Test Summary

Test	Why
[2,3]	Smallest nontrivial tree
[1,5,2]	Root with multiple children
[34,1,2]	Multi-digit masks
[3,22,5]	Invalid number inside subtree
[7]	Single valid node
[11]	Single invalid node
[12,34]	Completely compatible masks
[12,23]	Digit overlap across nodes
[22,33]	All values invalid
Chain of distinct digits	Deep tree structure
Large compatible masks	Stress subtree merging

Edge Cases

Values Containing Repeated Digits

A value such as 22, 101, or 777 is not valid even when selected alone. A common mistake is checking conflicts only between different nodes. The implementation detects duplicate digits while constructing the node mask and marks such values as invalid using -1, preventing them from ever being added to a subset.

Optimal Subset Does Not Include the Root

The subtree score is defined over any subset of nodes inside the subtree, not necessarily one containing the subtree root. For example, if the root value is invalid or conflicts with several large descendants, skipping the root may produce a better answer. The DP always keeps the empty state and never forces inclusion of the current node, so this case is handled naturally.

Multiple Children Producing Conflicting Digit Sets

Two different child subtrees may individually contain excellent solutions that cannot coexist because they use the same digit. The merge step explicitly checks:

(mask1 & mask2) == 0

before combining states. Therefore only globally valid digit assignments survive in the DP.

Entire Subtree Has No Valid Node

If every node in a subtree contains repeated digits, every node mask is invalid. The DP still contains the empty subset:

dp[0] = 0

so the maximum score becomes 0. This correctly reflects that no valid node can be selected.