Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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:
{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.{1}. The subset {3} is good. The score of this subset is 3.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:
{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.{1}. The subset {5} is good. The score of this subset is 5.{2}. The subset {2} is good. The score of this subset is 2.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:
{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.{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.{2}. The subset {2} is good. The score of this subset is 2.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:
{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.{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.{2}. The subset {5} is good. The score of this subset is 5.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 <= 5001 <= vals[i] <= 109par.length == npar[0] == -10 <= par[i] < n for i in [1, n - 1]par represents a valid tree.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Dynamic Programming · Bit Manipulation · Tree
[2,3] [-1,0]
[1,5,2] [-1,0,0]
[34,1,2] [-1,0,1]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3575: Maximum Good Subtree Score
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3575: Maximum Good Subtree Score
// package main
//
// import (
// "maps"
// "slices"
// )
//
// // https://space.bilibili.com/206214
// func goodSubtreeSum1(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// var dfs func(int) [1 << D]int
// dfs = func(x int) (f [1 << D]int) {
// // 计算 vals[x] 的数位集合 mask
// mask := 0
// for v := vals[x]; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 { // d 在集合 mask 中
// mask = 0 // 不符合要求
// break
// }
// mask |= 1 << d // 把 d 加到集合 mask 中
// }
//
// if mask > 0 {
// f[mask] = vals[x]
// }
//
// // 同一个集合 i 至多选一个，直接取 max
// for _, y := range g[x] {
// fy := dfs(y)
// for i, sum := range fy {
// f[i] = max(f[i], sum)
// }
// }
//
// for i := range f {
// // 枚举集合 i 的非空真子集
// for sub := i & (i - 1); sub > 0; sub = (sub - 1) & i {
// f[i] = max(f[i], f[sub]+f[i^sub])
// }
// }
//
// ans += slices.Max(f[:])
// return
// }
// dfs(0)
// return ans % mod
// }
//
// func goodSubtreeSumHSon(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// var init func(int) int
// init = func(x int) int {
// if g[x] == nil {
// return 1
// }
// size, hsz, hIdx := 1, 0, 0
// for i, y := range g[x] {
// sz := init(y)
// size += sz
// if sz > hsz {
// hsz, hIdx = sz, i
// }
// }
// // 把重儿子换到最前面
// g[x][0], g[x][hIdx] = g[x][hIdx], g[x][0]
// return size
// }
// init(0)
//
// type pair struct{ mask, val int }
// var dfs func(int) (map[int]int, []pair)
// dfs = func(x int) (f map[int]int, single []pair) {
// val := vals[x]
//
// // 计算 val 的数位集合 mask
// mask := 0
// for v := val; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 {
// mask = 0
// break
// }
// mask |= 1 << d
// }
//
// if g[x] == nil { // x 是叶子
// f = map[int]int{}
// if mask > 0 {
// ans += val
// f[mask] = val
// single = append(single, pair{mask, val})
// }
// return
// }
//
// f, single = dfs(g[x][0]) // 优先遍历重儿子
// update := func(msk, v int) {
// if v <= f[msk] {
// return
// }
// nf := maps.Clone(f)
// nf[msk] = v
// for msk2, s2 := range f {
// if msk&msk2 == 0 {
// nf[msk|msk2] = max(nf[msk|msk2], v+s2)
// }
// }
// f = nf
// }
//
// for _, y := range g[x][1:] {
// _, singleY := dfs(y)
// single = append(single, singleY...)
// // 把子树 y 中的 mask 和 val 一个一个地加到 f 中
// for _, p := range singleY {
// update(p.mask, p.val)
// }
// }
//
// if mask > 0 {
// update(mask, val)
// single = append(single, pair{mask, val})
// }
//
// mx := 0
// for _, s := range f {
// mx = max(mx, s)
// }
// ans += mx
//
// return
// }
// dfs(0)
// return ans % mod
// }
//
// func goodSubtreeSum(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// type pair struct{ mask, val int }
// var dfs func(int) (map[int]int, []pair)
// dfs = func(x int) (f map[int]int, single []pair) {
// f = map[int]int{}
//
// // 计算 val 的数位集合 mask
// val := vals[x]
// mask := 0
// for v := val; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 {
// mask = 0
// break
// }
// mask |= 1 << d
// }
//
// if mask > 0 {
// f[mask] = val
// single = append(single, pair{mask, val})
// }
//
// for _, y := range g[x] {
// fy, singleY := dfs(y)
//
// // 启发式合并
// if len(singleY) > len(single) {
// single, singleY = singleY, single
// f, fy = fy, f
// }
//
// single = append(single, singleY...)
//
// // 把子树 y 中的 mask 和 val 一个一个地加到 f 中
// for _, p := range singleY {
// msk, v := p.mask, p.val
// if v <= f[msk] {
// continue
// }
// nf := maps.Clone(f)
// nf[msk] = v
// for msk2, s2 := range f {
// if msk&msk2 == 0 {
// nf[msk|msk2] = max(nf[msk|msk2], v+s2)
// }
// }
// f = nf
// }
// }
//
// mx := 0
// for _, s := range f {
// mx = max(mx, s)
// }
// ans += mx
//
// return
// }
// dfs(0)
// return ans % mod
// }
// Accepted solution for LeetCode #3575: Maximum Good Subtree Score
package main
import (
"maps"
"slices"
)
// https://space.bilibili.com/206214
func goodSubtreeSum1(vals, par []int) (ans int) {
const mod = 1_000_000_007
const D = 10
n := len(par)
g := make([][]int, n)
for i := 1; i < n; i++ {
p := par[i]
g[p] = append(g[p], i)
}
var dfs func(int) [1 << D]int
dfs = func(x int) (f [1 << D]int) {
// 计算 vals[x] 的数位集合 mask
mask := 0
for v := vals[x]; v > 0; v /= D {
d := v % D
if mask>>d&1 > 0 { // d 在集合 mask 中
mask = 0 // 不符合要求
break
}
mask |= 1 << d // 把 d 加到集合 mask 中
}
if mask > 0 {
f[mask] = vals[x]
}
// 同一个集合 i 至多选一个，直接取 max
for _, y := range g[x] {
fy := dfs(y)
for i, sum := range fy {
f[i] = max(f[i], sum)
}
}
for i := range f {
// 枚举集合 i 的非空真子集
for sub := i & (i - 1); sub > 0; sub = (sub - 1) & i {
f[i] = max(f[i], f[sub]+f[i^sub])
}
}
ans += slices.Max(f[:])
return
}
dfs(0)
return ans % mod
}
func goodSubtreeSumHSon(vals, par []int) (ans int) {
const mod = 1_000_000_007
const D = 10
n := len(par)
g := make([][]int, n)
for i := 1; i < n; i++ {
p := par[i]
g[p] = append(g[p], i)
}
var init func(int) int
init = func(x int) int {
if g[x] == nil {
return 1
}
size, hsz, hIdx := 1, 0, 0
for i, y := range g[x] {
sz := init(y)
size += sz
if sz > hsz {
hsz, hIdx = sz, i
}
}
// 把重儿子换到最前面
g[x][0], g[x][hIdx] = g[x][hIdx], g[x][0]
return size
}
init(0)
type pair struct{ mask, val int }
var dfs func(int) (map[int]int, []pair)
dfs = func(x int) (f map[int]int, single []pair) {
val := vals[x]
// 计算 val 的数位集合 mask
mask := 0
for v := val; v > 0; v /= D {
d := v % D
if mask>>d&1 > 0 {
mask = 0
break
}
mask |= 1 << d
}
if g[x] == nil { // x 是叶子
f = map[int]int{}
if mask > 0 {
ans += val
f[mask] = val
single = append(single, pair{mask, val})
}
return
}
f, single = dfs(g[x][0]) // 优先遍历重儿子
update := func(msk, v int) {
if v <= f[msk] {
return
}
nf := maps.Clone(f)
nf[msk] = v
for msk2, s2 := range f {
if msk&msk2 == 0 {
nf[msk|msk2] = max(nf[msk|msk2], v+s2)
}
}
f = nf
}
for _, y := range g[x][1:] {
_, singleY := dfs(y)
single = append(single, singleY...)
// 把子树 y 中的 mask 和 val 一个一个地加到 f 中
for _, p := range singleY {
update(p.mask, p.val)
}
}
if mask > 0 {
update(mask, val)
single = append(single, pair{mask, val})
}
mx := 0
for _, s := range f {
mx = max(mx, s)
}
ans += mx
return
}
dfs(0)
return ans % mod
}
func goodSubtreeSum(vals, par []int) (ans int) {
const mod = 1_000_000_007
const D = 10
n := len(par)
g := make([][]int, n)
for i := 1; i < n; i++ {
p := par[i]
g[p] = append(g[p], i)
}
type pair struct{ mask, val int }
var dfs func(int) (map[int]int, []pair)
dfs = func(x int) (f map[int]int, single []pair) {
f = map[int]int{}
// 计算 val 的数位集合 mask
val := vals[x]
mask := 0
for v := val; v > 0; v /= D {
d := v % D
if mask>>d&1 > 0 {
mask = 0
break
}
mask |= 1 << d
}
if mask > 0 {
f[mask] = val
single = append(single, pair{mask, val})
}
for _, y := range g[x] {
fy, singleY := dfs(y)
// 启发式合并
if len(singleY) > len(single) {
single, singleY = singleY, single
f, fy = fy, f
}
single = append(single, singleY...)
// 把子树 y 中的 mask 和 val 一个一个地加到 f 中
for _, p := range singleY {
msk, v := p.mask, p.val
if v <= f[msk] {
continue
}
nf := maps.Clone(f)
nf[msk] = v
for msk2, s2 := range f {
if msk&msk2 == 0 {
nf[msk|msk2] = max(nf[msk|msk2], v+s2)
}
}
f = nf
}
}
mx := 0
for _, s := range f {
mx = max(mx, s)
}
ans += mx
return
}
dfs(0)
return ans % mod
}
# Accepted solution for LeetCode #3575: Maximum Good Subtree Score
#
# @lc app=leetcode id=3575 lang=python3
#
# [3575] Maximum Good Subtree Score
#
# @lc code=start
import sys
# Increase recursion depth for deep trees
sys.setrecursionlimit(2000)
class Solution:
def goodSubtreeSum(self, vals: List[int], par: List[int]) -> int:
n = len(vals)
children = [[] for _ in range(n)]
for i, p in enumerate(par):
if p != -1:
children[p].append(i)
# Precompute masks and validity for each node
node_masks = [0] * n
node_valid = [False] * n
for i, x in enumerate(vals):
s = str(x)
mask = 0
valid = True
used = 0
for c in s:
d = int(c)
if (used >> d) & 1:
valid = False
break
used |= (1 << d)
if valid:
node_masks[i] = used
node_valid[i] = True
ans = 0
MOD = 10**9 + 7
def dfs(u):
# Initialize DP state for the current node u
# dp[mask] = max_score
# Start with the empty set (score 0, mask 0)
current_dp = {0: 0}
# If the current node itself is valid, add it as a starting state
if node_valid[u]:
current_dp[node_masks[u]] = vals[u]
# Iterate through all children and merge their DP states
for v in children[u]:
child_dp = dfs(v)
# Convert to lists for iteration
l1 = list(current_dp.items())
l2 = list(child_dp.items())
# Temporary array for merging to avoid hash map overhead in the inner loop
# 1024 is 2^10, covering all possible digit masks
tmp = [-1] * 1024
# Merge logic: combine disjoint masks
for m1, s1 in l1:
for m2, s2 in l2:
if (m1 & m2) == 0:
nm = m1 | m2
ns = s1 + s2
if ns > tmp[nm]:
tmp[nm] = ns
# Rebuild the sparse dictionary for the next iteration
current_dp = {}
for m in range(1024):
if tmp[m] != -1:
current_dp[m] = tmp[m]
# The max score for the subtree rooted at u is the max value in current_dp
# Note: The empty set (score 0) is always present, so max is at least 0.
# If all values are positive, non-empty sets will have score > 0.
mx = 0
for s in current_dp.values():
if s > mx:
mx = s
nonlocal ans
ans = (ans + mx) % MOD
return current_dp
dfs(0)
return ans
# @lc code=end
// Accepted solution for LeetCode #3575: Maximum Good Subtree Score
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3575: Maximum Good Subtree Score
// package main
//
// import (
// "maps"
// "slices"
// )
//
// // https://space.bilibili.com/206214
// func goodSubtreeSum1(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// var dfs func(int) [1 << D]int
// dfs = func(x int) (f [1 << D]int) {
// // 计算 vals[x] 的数位集合 mask
// mask := 0
// for v := vals[x]; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 { // d 在集合 mask 中
// mask = 0 // 不符合要求
// break
// }
// mask |= 1 << d // 把 d 加到集合 mask 中
// }
//
// if mask > 0 {
// f[mask] = vals[x]
// }
//
// // 同一个集合 i 至多选一个，直接取 max
// for _, y := range g[x] {
// fy := dfs(y)
// for i, sum := range fy {
// f[i] = max(f[i], sum)
// }
// }
//
// for i := range f {
// // 枚举集合 i 的非空真子集
// for sub := i & (i - 1); sub > 0; sub = (sub - 1) & i {
// f[i] = max(f[i], f[sub]+f[i^sub])
// }
// }
//
// ans += slices.Max(f[:])
// return
// }
// dfs(0)
// return ans % mod
// }
//
// func goodSubtreeSumHSon(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// var init func(int) int
// init = func(x int) int {
// if g[x] == nil {
// return 1
// }
// size, hsz, hIdx := 1, 0, 0
// for i, y := range g[x] {
// sz := init(y)
// size += sz
// if sz > hsz {
// hsz, hIdx = sz, i
// }
// }
// // 把重儿子换到最前面
// g[x][0], g[x][hIdx] = g[x][hIdx], g[x][0]
// return size
// }
// init(0)
//
// type pair struct{ mask, val int }
// var dfs func(int) (map[int]int, []pair)
// dfs = func(x int) (f map[int]int, single []pair) {
// val := vals[x]
//
// // 计算 val 的数位集合 mask
// mask := 0
// for v := val; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 {
// mask = 0
// break
// }
// mask |= 1 << d
// }
//
// if g[x] == nil { // x 是叶子
// f = map[int]int{}
// if mask > 0 {
// ans += val
// f[mask] = val
// single = append(single, pair{mask, val})
// }
// return
// }
//
// f, single = dfs(g[x][0]) // 优先遍历重儿子
// update := func(msk, v int) {
// if v <= f[msk] {
// return
// }
// nf := maps.Clone(f)
// nf[msk] = v
// for msk2, s2 := range f {
// if msk&msk2 == 0 {
// nf[msk|msk2] = max(nf[msk|msk2], v+s2)
// }
// }
// f = nf
// }
//
// for _, y := range g[x][1:] {
// _, singleY := dfs(y)
// single = append(single, singleY...)
// // 把子树 y 中的 mask 和 val 一个一个地加到 f 中
// for _, p := range singleY {
// update(p.mask, p.val)
// }
// }
//
// if mask > 0 {
// update(mask, val)
// single = append(single, pair{mask, val})
// }
//
// mx := 0
// for _, s := range f {
// mx = max(mx, s)
// }
// ans += mx
//
// return
// }
// dfs(0)
// return ans % mod
// }
//
// func goodSubtreeSum(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// type pair struct{ mask, val int }
// var dfs func(int) (map[int]int, []pair)
// dfs = func(x int) (f map[int]int, single []pair) {
// f = map[int]int{}
//
// // 计算 val 的数位集合 mask
// val := vals[x]
// mask := 0
// for v := val; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 {
// mask = 0
// break
// }
// mask |= 1 << d
// }
//
// if mask > 0 {
// f[mask] = val
// single = append(single, pair{mask, val})
// }
//
// for _, y := range g[x] {
// fy, singleY := dfs(y)
//
// // 启发式合并
// if len(singleY) > len(single) {
// single, singleY = singleY, single
// f, fy = fy, f
// }
//
// single = append(single, singleY...)
//
// // 把子树 y 中的 mask 和 val 一个一个地加到 f 中
// for _, p := range singleY {
// msk, v := p.mask, p.val
// if v <= f[msk] {
// continue
// }
// nf := maps.Clone(f)
// nf[msk] = v
// for msk2, s2 := range f {
// if msk&msk2 == 0 {
// nf[msk|msk2] = max(nf[msk|msk2], v+s2)
// }
// }
// f = nf
// }
// }
//
// mx := 0
// for _, s := range f {
// mx = max(mx, s)
// }
// ans += mx
//
// return
// }
// dfs(0)
// return ans % mod
// }
// Accepted solution for LeetCode #3575: Maximum Good Subtree Score
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3575: Maximum Good Subtree Score
// package main
//
// import (
// "maps"
// "slices"
// )
//
// // https://space.bilibili.com/206214
// func goodSubtreeSum1(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// var dfs func(int) [1 << D]int
// dfs = func(x int) (f [1 << D]int) {
// // 计算 vals[x] 的数位集合 mask
// mask := 0
// for v := vals[x]; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 { // d 在集合 mask 中
// mask = 0 // 不符合要求
// break
// }
// mask |= 1 << d // 把 d 加到集合 mask 中
// }
//
// if mask > 0 {
// f[mask] = vals[x]
// }
//
// // 同一个集合 i 至多选一个，直接取 max
// for _, y := range g[x] {
// fy := dfs(y)
// for i, sum := range fy {
// f[i] = max(f[i], sum)
// }
// }
//
// for i := range f {
// // 枚举集合 i 的非空真子集
// for sub := i & (i - 1); sub > 0; sub = (sub - 1) & i {
// f[i] = max(f[i], f[sub]+f[i^sub])
// }
// }
//
// ans += slices.Max(f[:])
// return
// }
// dfs(0)
// return ans % mod
// }
//
// func goodSubtreeSumHSon(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// var init func(int) int
// init = func(x int) int {
// if g[x] == nil {
// return 1
// }
// size, hsz, hIdx := 1, 0, 0
// for i, y := range g[x] {
// sz := init(y)
// size += sz
// if sz > hsz {
// hsz, hIdx = sz, i
// }
// }
// // 把重儿子换到最前面
// g[x][0], g[x][hIdx] = g[x][hIdx], g[x][0]
// return size
// }
// init(0)
//
// type pair struct{ mask, val int }
// var dfs func(int) (map[int]int, []pair)
// dfs = func(x int) (f map[int]int, single []pair) {
// val := vals[x]
//
// // 计算 val 的数位集合 mask
// mask := 0
// for v := val; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 {
// mask = 0
// break
// }
// mask |= 1 << d
// }
//
// if g[x] == nil { // x 是叶子
// f = map[int]int{}
// if mask > 0 {
// ans += val
// f[mask] = val
// single = append(single, pair{mask, val})
// }
// return
// }
//
// f, single = dfs(g[x][0]) // 优先遍历重儿子
// update := func(msk, v int) {
// if v <= f[msk] {
// return
// }
// nf := maps.Clone(f)
// nf[msk] = v
// for msk2, s2 := range f {
// if msk&msk2 == 0 {
// nf[msk|msk2] = max(nf[msk|msk2], v+s2)
// }
// }
// f = nf
// }
//
// for _, y := range g[x][1:] {
// _, singleY := dfs(y)
// single = append(single, singleY...)
// // 把子树 y 中的 mask 和 val 一个一个地加到 f 中
// for _, p := range singleY {
// update(p.mask, p.val)
// }
// }
//
// if mask > 0 {
// update(mask, val)
// single = append(single, pair{mask, val})
// }
//
// mx := 0
// for _, s := range f {
// mx = max(mx, s)
// }
// ans += mx
//
// return
// }
// dfs(0)
// return ans % mod
// }
//
// func goodSubtreeSum(vals, par []int) (ans int) {
// const mod = 1_000_000_007
// const D = 10
// n := len(par)
// g := make([][]int, n)
// for i := 1; i < n; i++ {
// p := par[i]
// g[p] = append(g[p], i)
// }
//
// type pair struct{ mask, val int }
// var dfs func(int) (map[int]int, []pair)
// dfs = func(x int) (f map[int]int, single []pair) {
// f = map[int]int{}
//
// // 计算 val 的数位集合 mask
// val := vals[x]
// mask := 0
// for v := val; v > 0; v /= D {
// d := v % D
// if mask>>d&1 > 0 {
// mask = 0
// break
// }
// mask |= 1 << d
// }
//
// if mask > 0 {
// f[mask] = val
// single = append(single, pair{mask, val})
// }
//
// for _, y := range g[x] {
// fy, singleY := dfs(y)
//
// // 启发式合并
// if len(singleY) > len(single) {
// single, singleY = singleY, single
// f, fy = fy, f
// }
//
// single = append(single, singleY...)
//
// // 把子树 y 中的 mask 和 val 一个一个地加到 f 中
// for _, p := range singleY {
// msk, v := p.mask, p.val
// if v <= f[msk] {
// continue
// }
// nf := maps.Clone(f)
// nf[msk] = v
// for msk2, s2 := range f {
// if msk&msk2 == 0 {
// nf[msk|msk2] = max(nf[msk|msk2], v+s2)
// }
// }
// f = nf
// }
// }
//
// mx := 0
// for _, s := range f {
// mx = max(mx, s)
// }
// ans += mx
//
// return
// }
// dfs(0)
// return ans % mod
// }
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.