解题思路本题采用 树形 DP 状态压缩bitmask1. 状态表示十进制只有 10 个数字0-9用 10 位 mask 表示已使用的数字集合。2. DP 定义对每个节点 u维护一个哈希表 dp: HashMapmask, max_score表示在该子树中达到某 mask 的最大分数。3. 空集初始化dp[0] 0空集始终合法。4. 处理当前节点若 vals[u] 自身无重复数字计算其 mask更新 dp[mask]。5. 合并子节点对每个子节点返回的 child_dp枚举当前 dp 与 child_dp 的所有 mask 对若 mask1 mask2 0数字不冲突则合并为 mask1 | mask2分数相加并取最大值。6. 收集答案每个节点的 maxScore[u] 即该节点 dp 中所有分数的最大值累加到答案。Rust 实现rustuse std::collections::HashMap;impl Solution {pub fn good_subtree_sum(vals: Veci32, par: Veci32) - i32 {const MOD: i64 1_000_000_007;let n vals.len();// 建树记录每个节点的子节点let mut children vec![Vec::new(); n];for i in 1..n {children[par[i] as usize].push(i);}let mut ans 0i64;// 判断数值自身是否包含重复数字fn has_unique_digits(mut x: i32) - bool {let mut seen 0u16;while x 0 {let d x % 10;let bit 1 d;if seen bit ! 0 {return false;}seen | bit;x / 10;}true}// 计算数值对应的 maskfn calc_mask(mut x: i32) - u16 {let mut mask 0u16;while x 0 {let d x % 10;mask | 1 d;x / 10;}mask}// DFS返回该子树对应的 dp 哈希表fn dfs(u: usize,vals: Veci32,children: VecVecusize,ans: mut i64,) - HashMapu16, i64 {let mut dp HashMap::new();dp.insert(0, 0); // 空集// 处理当前节点自身let val vals[u];if has_unique_digits(val) {let mask calc_mask(val);let score val as i64;dp.entry(mask).and_modify(|e| *e (*e).max(score)).or_insert(score);}// 合并所有子节点for v in children[u] {let child_dp dfs(v, vals, children, ans);let mut new_dp dp.clone();for (mask1, score1) in dp.iter() {for (mask2, score2) in child_dp.iter() {if mask1 mask2 0 {let new_mask mask1 | mask2;let new_score score1 score2;new_dp.entry(new_mask).and_modify(|e| *e (*e).max(new_score)).or_insert(new_score);}}}dp new_dp;}// 当前节点的 maxScore 是 dp 中的最大分数if let Some(max_score) dp.values().max() {*ans (*ans max_score) % MOD;}dp}dfs(0, vals, children, mut ans);ans as i32}}复杂度分析· 时间复杂度O(n * 4^D)其中 D 10。每个节点合并子节点时需枚举两层的 mask 组合最多 2^10 × 2^10。但由于要求 mask1 mask2 0实际枚举量远小于上限。· 空间复杂度O(n * 2^D)递归栈 每个节点存储的 dp 哈希表。关键点1. 数值自身去重若 vals[i] 包含重复数字如 22则该节点不能单独加入任何好子集。2. 空集始终合法分数为 0确保每个节点的 maxScore 至少为 0。3. 模运算答案对 10^97 取模累加时及时取模防止溢出。