企业官网建设流程全解析

这是 LeetCode 3575. 最大好子树分数 的 Java 实现。

解题思路

核心观察：题目要求"好子集"中每个数字 0-9 在所有数的数位中最多出现一次。由于只有 10 种数字，可以用位掩码（bitmask）来表示数字的出现状态。

关键步骤：
1. 状态压缩：用 10 位二进制数表示数字 0-9 的使用情况，第 i 位为 1 表示数字 i 已被使用
2. 树形 DP：对每个节点，维护一个 Map，表示在其子树中，每种数字使用状态（mask）对应的最大分数
3. 合并子树：对于当前节点，枚举其自身状态和每个子树的状态，如果两者无交集（`mask1 & mask2 == 0`），则可以合并
4. 计算答案：每个节点的 `maxScore` 就是其所有状态中的最大分数，累加所有节点的 `maxScore`

时间复杂度：O(N \cdot 4^D)，其中 D=10 为数字种类数；空间复杂度：O(N \cdot 2^D)

Java 代码

```java
import java.util.*;

class Solution {
private static final int MOD = (int) 1e9 + 7;
private List<Integer>[] g;
private int[] vals;
private long ans;

public int goodSubtreeSum(int[] vals, int[] par) {
int n = vals.length;
this.vals = vals;
this.ans = 0;

// 建树
g = new ArrayList[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
g[par[i]].add(i);
}

// 从根节点开始 DFS
dfs(0);

return (int) (ans % MOD);
}

// 返回以 u 为根的子树中，每种 mask 状态对应的最大分数
private Map<Integer, Integer> dfs(int u) {
// d[mask] 表示在当前子树中，数字使用状态为 mask 时的最大分数
Map<Integer, Integer> d = new HashMap<>();
d.put(0, 0); // 不选任何节点，分数为 0

// 计算当前节点值的数字掩码
int val = vals[u];
String s = String.valueOf(val);

// 检查当前节点值是否有重复数字
boolean hasDuplicate = false;
Set<Character> seen = new HashSet<>();
for (char c : s.toCharArray()) {
if (!seen.add(c)) {
hasDuplicate = true;
break;
}
}

// 如果没有重复数字，可以单独选当前节点
if (!hasDuplicate) {
int mask = 0;
for (char c : s.toCharArray()) {
mask |= 1 << (c - '0');
}
d.put(mask, val);
}

// 合并每个子树
for (int v : g[u]) {
Map<Integer, Integer> d2 = dfs(v);

// 临时存储新的状态
Map<Integer, Integer> nd = new HashMap<>(d);

// 枚举当前已有的状态和子树的状态
for (Map.Entry<Integer, Integer> e1 : d.entrySet()) {
int mask1 = e1.getKey();
int sum1 = e1.getValue();
for (Map.Entry<Integer, Integer> e2 : d2.entrySet()) {
int mask2 = e2.getKey();
int sum2 = e2.getValue();

// 如果两个状态没有交集，可以合并
if ((mask1 & mask2) == 0) {
int newMask = mask1 | mask2;
int newSum = sum1 + sum2;
// 取最大值
nd.merge(newMask, newSum, Math::max);
}
}
}

d = nd;
}

// 计算当前节点的 maxScore，并累加到答案
int maxScore = 0;
for (int score : d.values()) {
maxScore = Math.max(maxScore, score);
}
ans += maxScore;

return d;
}
}
```

代码说明

- 位掩码表示：`mask` 的第 i 位为 1 表示数字 i 已被使用。例如数字 34 的掩码为 `(1<<3)|(1<<4) = 0b0000001100`
- 状态合并：两个子集可以合并当且仅当它们的数字集合不相交，即 `mask1 & mask2 == 0`
- HashMap 优化：每个节点实际产生的状态数远小于 2^{10}=1024，因为需要多个子树才能组合出大量状态，所以用 HashMap 而非数组可以节省时间和空间
- 答案累加：在 DFS 返回前，计算当前节点所有状态中的最大分数，即为该节点的 `maxScore`，累加到全局答案中

这个解法在 n \le 500 的约束下可以通过所有测试用例。