解题思路采用 树形 DP 状态压缩bitmask· 十进制数字只有 10 种0~9用 10 位掩码表示已使用的数字集合。· 对每个节点 u维护一个数组 dp[1024]其中 dp[mask] 表示该子树中达到该 mask 的最大分数-1 表示不可达。· 空集 mask0分数为 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;}// 计算一个数字对应的 bitmaskint 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));// 枚举两表所有有效 maskfor (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^97 取模累加时及时取模。