DeepSeek LeetCode 3575. 最大好子树分数 C语言实现

解题思路

采用 树形 DP + 状态压缩（bitmask）：

· 十进制数字只有 10 种（0~9），用 10 位掩码表示已使用的数字集合。
· 对每个节点 u，维护一个数组 dp[1024]，其中 dp[mask] 表示该子树中达到该 mask 的最大分数，-1 表示不可达。
· 空集 mask=0，分数为 0，始终合法。
· 处理当前节点自身：若 vals[u] 中无重复数字，计算其 mask，并用 vals[u] 更新 dp[mask]。
· 合并子节点：对每个子节点返回的 child_dp，枚举所有 mask 对，若无交集（mask1 & mask2 == 0），则合并为 mask1 | mask2，分数相加，更新最大分数。
· 每个节点的 maxScore[u] 即为该节点 dp 中所有分数最大值（至少为 0），累加到答案并取模。

C 语言实现

```c
#include <stdlib.h>
#include <string.h>

#define MAX_MASK 1024
#define MOD 1000000007

// 判断数字各位是否互不相同（不含重复数字）
int has_unique_digits(int x) {
int seen = 0;
if (x == 0) return 1; // 0 只含一个数字
while (x > 0) {
int d = x % 10;
int bit = 1 << d;
if (seen & bit) return 0;
seen |= bit;
x /= 10;
}
return 1;
}

// 计算一个数字对应的 bitmask
int calc_mask(int x) {
int mask = 0;
if (x == 0) return 1 << 0;
while (x > 0) {
int d = x % 10;
mask |= 1 << d;
x /= 10;
}
return mask;
}

// DFS 返回该子树的 dp 数组（动态分配）
int* dfs(int u, int* vals, int** children, int* child_count, int* ans) {
int* dp = (int*)malloc(MAX_MASK * sizeof(int));
for (int i = 0; i < MAX_MASK; i++) dp[i] = -1;
dp[0] = 0; // 空集

// 处理当前节点自身的值
int val = vals[u];
if (has_unique_digits(val)) {
int mask = calc_mask(val);
if (val > dp[mask]) dp[mask] = val;
}

// 合并所有子节点
for (int i = 0; i < child_count[u]; i++) {
int v = children[u][i];
int* child_dp = dfs(v, vals, children, child_count, ans);

// 复制当前 dp 作为新表
int* new_dp = (int*)malloc(MAX_MASK * sizeof(int));
memcpy(new_dp, dp, MAX_MASK * sizeof(int));

// 枚举两表所有有效 mask
for (int m1 = 0; m1 < MAX_MASK; m1++) {
if (dp[m1] < 0) continue;
for (int m2 = 0; m2 < MAX_MASK; m2++) {
if (child_dp[m2] < 0) continue;
if ((m1 & m2) == 0) { // 数字不冲突
int nm = m1 | m2;
int ns = dp[m1] + child_dp[m2];
if (ns > new_dp[nm]) new_dp[nm] = ns;
}
}
}

free(dp);
free(child_dp);
dp = new_dp;
}

// 当前节点的 maxScore 为 dp 中的最大值
int max_score = 0;
for (int i = 0; i < MAX_MASK; i++) {
if (dp[i] > max_score) max_score = dp[i];
}
*ans = (*ans + max_score) % MOD;

return dp;
}

int goodSubtreeSum(int* vals, int valsSize, int* par, int parSize) {
// 建树（邻接表）
int** children = (int**)malloc(valsSize * sizeof(int*));
int* child_count = (int*)calloc(valsSize, sizeof(int));

for (int i = 1; i < valsSize; i++) {
child_count[par[i]]++;
}
for (int i = 0; i < valsSize; i++) {
children[i] = (int*)malloc(child_count[i] * sizeof(int));
}
int* cur = (int*)calloc(valsSize, sizeof(int));
for (int i = 1; i < valsSize; i++) {
int p = par[i];
children[p][cur[p]++] = i;
}
free(cur);

int ans = 0;
int* root_dp = dfs(0, vals, children, child_count, &ans);
free(root_dp);

// 释放树内存
for (int i = 0; i < valsSize; i++) free(children[i]);
free(children);
free(child_count);

return ans;
}
```

复杂度分析

· 时间复杂度：每个节点合并子节点时，最坏需枚举 2^10 × 2^10 = 1,048,576 种组合，但实际有效状态远少于此。若假设节点数为 n，复杂度约为 O(n * 有效状态数²)，在本题数据范围内可行。
· 空间复杂度：每个节点在递归中维护一个 dp 数组（长度 1024），递归栈深度为树高，空间约 O(n * 1024)，但递归返回后释放，实际峰值约为 O(树高 * 1024)。

关键点

· 数值自身含重复数字时，不能加入任何好子集。
· 空集始终合法，因此每个节点的 maxScore 至少为 0。
· 答案对 10^9+7 取模，累加时及时取模。