2025-11-22：最大好子树分数。用go语言，给定一棵以节点 0 为根的无向树，节点编号为 0 到 n-1。每个节点 i 有一个整数值 vals[i]，其父节点由数组 par 给出。

对任一节点 u，考虑以 u 为根的那棵包含 u 本身及其所有后代的子树。在这棵子树里任选若干节点（可以不选），把它们的值组成一个集合。如果把这些被选数值按十进制展开后，所有数位中每个十进制数字 0 到 9 在所有数位上最多出现一次，则称该选取是合法的。这样的集合的得分定义为所选节点值之和。

令 maxScore[u] 表示在以 u 为根的子树内可以取得的合法集合的最大得分。问题要求返回所有 maxScore[u] 的总和（对 1000000007 取模）。

（说明：允许选空集合，其得分为 0；“每个数字最多出现一次”是对所有被选数值的所有数位的全局限制。）

1 <= n == vals.length <= 500。

1 <= vals[i] <= 1000000000。

par.length == n。

par[0] == -1。

对于 [1, n - 1] 中的每一个 i ，都有 0 <= par[i] < n 。

输入生成保证父数组 par 表示一棵有效的树。

输入: vals = [3,22,5], par = [-1,0,1]。

输出: 18。

解释:

以节点 0 为根的子树包括节点 {0, 1, 2}。子集 {3, 22, 5} 不是好子集，因为数字 2 出现两次。子集 {3, 5} 是好子集，此子集的分数是 3 + 5 = 8。

以节点 1 为根的子树包括节点 {1, 2}。子集 {22, 5} 不是好子集，因为数字 2 出现两次。子集 {5} 是好子集，此子集的分数是 5。

以节点 2 为根的子树包括 {2}。子集 {5} 是 好的。此子集的分数是 5。

maxScore 数组为 [8, 5, 5]，并且 maxScore 中所有值的总和是 8 + 5 + 5 = 18。因此，答案是 18。

题目来自力扣3575。

🔍 步骤一：预处理与初始化

代码首先进行一些预处理工作：

• 定义常量，包括模数 mod 和进制基数 D=10（代表十进制）。
• 根据父节点数组 par 构建树的邻接表 g，用于表示节点间的父子关系。例如，g[p] 存储了节点 p 的所有直接子节点。
• 定义核心的数据结构 pair，用于记录一个“合法数字集合”的状态。其中 mask 是一个位掩码（bitmask），表示该集合中所有数字的十进制数位使用情况（例如，第 d 位为1表示数字 d 已经出现过）；val 表示构成这个集合的所有节点值之和。

🌳 步骤二：深度优先搜索（DFS）

对树进行深度优先遍历（DFS），从根节点（节点0）开始。DFS函数 dfs(x) 返回两个值：

1. f map[int]int：一个映射。键是位掩码 mask，值是在以节点 x 为根的子树中，能够形成该掩码的所有合法节点集合的最大和（val）。这相当于记录了在子树 x 内，各种不同数位组合下能获得的最大分数。
2. single []pair：一个列表，存储了所有仅包含单个节点的合法状态（即只选子树 x 中的某一个节点构成的合法集合）。这个列表主要用于后续的合并操作。

🔢 步骤三：处理当前节点

对于当前遍历到的节点 x：

1. 计算节点值的数位掩码：将节点值 vals[x] 的各个十进制数位提取出来。如果在提取过程中发现某个数字重复出现（通过检查位掩码的相应位是否已置1），则判定该节点值本身非法，其掩码 mask 被设为0。否则，掩码 mask 记录所有出现过的数字。
2. 初始化状态：如果节点 x 的值本身是合法的（mask > 0），那么就将这个单节点状态 {mask, val} 加入到 f 映射和 single 列表中。

🔁 步骤四：合并子树信息

这是算法的核心部分。节点 x 需要合并其所有子节点 y 传递上来的状态信息 (fy 和 singleY)。

• 启发式合并（小的合并到大的）：为了提高效率，代码采用了启发式合并策略。在合并子节点 y 的状态之前，会比较当前已合并的 single 列表和子节点 y 的 singleY 列表的长度。如果 singleY 更长，就交换两者的内容，确保总是将较小的集合合并到较大的集合中。这能有效降低合并操作的总时间复杂度。
• 状态合并与更新：合并过程遍历子节点 y 的 singleY 列表中的每一个状态 p。对于每个状态 p：
  • 检查其值 v 是否大于当前 f 映射中相同掩码 msk 对应的值。如果不是，则跳过，因为我们要的是最大和。
  • 如果 v 更大，则创建一个新的状态映射 nf（初始为 f 的副本），并更新 nf[msk] 的值为 v。
  • 然后，将新状态 p 的掩码 msk 与 f 映射中所有已有的掩码 msk2 进行组合。如果 msk 和 msk2 没有公共数位（即 msk & msk2 == 0），说明这两个数字集合可以合并成一个新的、数位仍然不重复的更大集合。计算新集合的和 v + s2，并尝试更新 nf[msk|msk2] 的值，记录更大的和。
  • 完成所有组合检查后，将 f 更新为 nf。

💯 步骤五：计算当前子树的最大分数并累加答案

在合并完所有子节点的状态后，遍历当前节点 x 的最终状态映射 f，找到其中所有合法节点集合的最大和 mx。将这个最大值 mx 累加到全局答案 ans 中。这步对应计算题目要求的 maxScore[u]。

⏱️ 步骤六：复杂度分析

• 时间复杂度：最坏情况下，每个节点的 single 列表可能包含 O(2^10) = O(1024) 种不同的数位掩码状态（因为数字0-9最多10位）。在合并子树时，需要组合这些状态。由于采用了启发式合并，合并操作的总时间复杂度可以优化到大约 O(n * logn * 2^(2*10))。考虑到 n <= 500，这个复杂度在可接受范围内。主导项是状态合并部分。
• 额外空间复杂度：主要消耗在DFS递归调用栈和存储每个节点的状态映射 f 及列表 single 上。递归栈深度为树高，最坏情况O(n)。每个节点存储的状态数量最多为 O(2^10)。因此，总的空间复杂度约为 O(n * 2^10)。

💎 总结

这个解决方案的核心思想是使用深度优先搜索结合动态规划和位掩码技术，通过启发式合并来高效地计算每个子树中满足特定数位不重复条件的最大节点值之和。

Go完整代码如下：

package main

import (
	"fmt"
	"maps"
)

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
}

func main() {
	vals := []int{3, 22, 5}
	par := []int{-1, 0, 1}
	result := goodSubtreeSum(vals, par)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List, Dict, Tuple
import copy

def goodSubtreeSum(vals: List[int], par: List[int]) -> int:
    mod = 1_000_000_007
    D = 10
    n = len(par)
    
    # 构建树结构
    g = [[] for _ in range(n)]
    for i in range(1, n):
        p = par[i]
        g[p].append(i)
    
    ans = 0
    
    def dfs(x: int) -> Tuple[Dict[int, int], List[Tuple[int, int]]]:
        nonlocal ans
        f = {}
        
        # 计算 val 的数位集合 mask
        val = vals[x]
        mask = 0
        v = val
        valid_mask = True
        
        while v > 0:
            d = v % D
            if mask >> d & 1:
                valid_mask = False
                break
            mask |= 1 << d
            v //= D
        
        single = []
        if valid_mask and mask > 0:
            f[mask] = val
            single.append((mask, val))
        
        for y in g[x]:
            fy, singleY = dfs(y)
            
            # 启发式合并：确保 single 是较大的那个
            if len(singleY) > len(single):
                single, singleY = singleY, single
                f, fy = fy, f
            
            single.extend(singleY)
            
            # 把子树 y 中的 mask 和 val 一个一个地加到 f 中
            for msk, v in singleY:
                if v <= f.get(msk, 0):
                    continue
                    
                nf = copy.deepcopy(f)
                nf[msk] = v
                
                for msk2, s2 in f.items():
                    if msk & msk2 == 0:
                        combined_mask = msk | msk2
                        nf[combined_mask] = max(nf.get(combined_mask, 0), v + s2)
                
                f = nf
        
        # 更新答案
        mx = 0
        for s in f.values():
            mx = max(mx, s)
        ans += mx
        
        return f, single
    
    dfs(0)
    return ans % mod

def main():
    vals = [3, 22, 5]
    par = [-1, 0, 1]
    result = goodSubtreeSum(vals, par)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <functional>

using namespace std;

int goodSubtreeSum(vector<int>& vals, vector<int>& par) {
    const int mod = 1000000007;
    const int D = 10;
    int n = par.size();

    // 构建树结构
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int p = par[i];
        g[p].push_back(i);
    }

    int ans = 0;

    // 使用pair表示mask和val
    using Pair = pair<int, int>;

    function<tuple<unordered_map<int, int>, vector<Pair>>(int)> dfs;
    dfs = [&](int x) -> tuple<unordered_map<int, int>, vector<Pair>> {
        unordered_map<int, int> f;
        vector<Pair> single;

        // 计算val的数位集合mask
        int val = vals[x];
        int mask = 0;
        int v = val;
        bool valid_mask = true;

        while (v > 0) {
            int d = v % D;
            if (mask >> d & 1) {
                valid_mask = false;
                break;
            }
            mask |= 1 << d;
            v /= D;
        }

        if (valid_mask && mask > 0) {
            f[mask] = val;
            single.emplace_back(mask, val);
        }

        for (int y : g[x]) {
            auto [fy, singleY] = dfs(y);

            // 启发式合并：确保single是较大的那个
            if (singleY.size() > single.size()) {
                swap(single, singleY);
                swap(f, fy);
            }

            single.insert(single.end(), singleY.begin(), singleY.end());

            // 把子树y中的mask和val一个一个地加到f中
            for (auto [msk, v_val] : singleY) {
                if (v_val <= f[msk]) {
                    continue;
                }

                unordered_map<int, int> nf = f;
                nf[msk] = v_val;

                for (auto [msk2, s2] : f) {
                    if ((msk & msk2) == 0) {
                        int combined_mask = msk | msk2;
                        nf[combined_mask] = max(nf[combined_mask], v_val + s2);
                    }
                }

                f = move(nf);
            }
        }

        // 更新答案
        int mx = 0;
        for (auto [_, s] : f) {
            mx = max(mx, s);
        }
        ans = (ans + mx) % mod;

        return {f, single};
    };

    dfs(0);
    return ans;
}

int main() {
    vector<int> vals = {3, 22, 5};
    vector<int> par = {-1, 0, 1};
    int result = goodSubtreeSum(vals, par);
    cout << result << endl;
    return 0;
}