Hard
题目描述
给定一个以节点 0 为根的无向树，有 n 个节点，编号从 0 到 n - 1。每个节点 i 有一个整数值 vals[i]，其父节点由 par[i] 给出。
如果一个节点子树内的节点子集满足：所选节点值的十进制表示中，数字 0 到 9 每个最多出现一次，则称该子集为"好"子集。
好子集的分数是其节点值的总和。
定义长度为 n 的数组 maxScore，其中 maxScore[u] 表示以节点 u 为根的子树中（包括 u 本身及其所有后代）好子集的最大可能分数。
返回 maxScore 中所有值的总和。
由于答案可能很大，请返回结果对 109 + 7 取模。
示例 1：
输入：vals = [2,3], par = [-1,0]
输出：8
解释：
- 以节点 0 为根的子树包括节点 {0, 1}。子集 {2, 3} 是好的，因为数字 2 和 3 只出现一次。此子集的分数是 2 + 3 = 5。
- 以节点 1 为根的子树只包括节点 {1}。子集 {3} 是好的。此子集的分数是 3。
- maxScore 数组是 [5, 3]，所有值的总和是 5 + 3 = 8。
示例 2：
输入：vals = [1,5,2], par = [-1,0,0]
输出：15
示例 3：
输入：vals = [34,1,2], par = [-1,0,1]
输出：42
示例 4：
输入：vals = [3,22,5], par = [-1,0,1]
输出：18
约束：
- 1 <= n == vals.length <= 500
- 1 <= vals[i] <= 109
- par.length == n
- par[0] == -1
- 0 <= par[i] < n for i in [1, n - 1]
- 输入保证父节点数组 par 表示一个有效的树
解题思路
这是一个树形动态规划问题，核心在于用位掩码表示数字的使用状态。
主要思路：
状态表示：使用 10 位的二进制数表示数字 0-9 的使用情况，第 i 位为 1 表示数字 i 已被使用。
获取数字掩码：对于每个节点值，提取其包含的所有数字，转换为对应的位掩码。如果某个数字在值中出现多次，该节点就不能单独形成好子集。
树形DP：对于每个节点，维护一个映射
mask -> maxSum，表示在当前掩码状态下能获得的最大分数。- 从子节点收集所有可能的状态
- 尝试将当前节点加入每个可能的状态中
- 状态转移时检查掩码冲突
状态合并：当处理多个子节点时，需要合并不同子树的状态。两个状态可以合并当且仅当它们的掩码没有重叠位。
答案计算：对每个节点，找出其子树中所有可能状态的最大值，累加得到最终答案。
优化要点：
- 预处理每个节点值的数字掩码
- 使用哈希表高效存储和查找状态
- 剪枝：如果节点值本身包含重复数字，跳过该节点
代码实现
class Solution {
public:
int goodSubtreeSum(vector<int>& vals, vector<int>& par) {
const int MOD = 1e9 + 7;
int n = vals.size();
// 构建邻接表
vector<vector<int>> children(n);
for (int i = 1; i < n; i++) {
children[par[i]].push_back(i);
}
// 获取数字的掩码
auto getMask = [](int val) {
int mask = 0;
while (val > 0) {
int digit = val % 10;
if (mask & (1 << digit)) return -1; // 重复数字
mask |= (1 << digit);
val /= 10;
}
return mask;
};
vector<int> masks(n);
for (int i = 0; i < n; i++) {
masks[i] = getMask(vals[i]);
}
long long totalSum = 0;
// 树形DP
function<unordered_map<int, long long>(int)> dfs = [&](int u) -> unordered_map<int, long long> {
unordered_map<int, long long> dp;
dp[0] = 0; // 空集
// 处理所有子节点
for (int v : children[u]) {
auto childDp = dfs(v);
unordered_map<int, long long> newDp;
// 合并当前状态和子节点状态
for (auto& [mask1, sum1] : dp) {
for (auto& [mask2, sum2] : childDp) {
if ((mask1 & mask2) == 0) { // 没有重叠
int newMask = mask1 | mask2;
newDp[newMask] = max(newDp[newMask], sum1 + sum2);
}
}
}
dp = move(newDp);
}
// 尝试加入当前节点
if (masks[u] != -1) {
unordered_map<int, long long> newDp = dp;
for (auto& [mask, sum] : dp) {
if ((mask & masks[u]) == 0) {
int newMask = mask | masks[u];
newDp[newMask] = max(newDp[newMask], sum + vals[u]);
}
}
dp = move(newDp);
}
// 计算当前子树的最大值
long long maxVal = 0;
for (auto& [mask, sum] : dp) {
maxVal = max(maxVal, sum);
}
totalSum = (totalSum + maxVal) % MOD;
return dp;
};
dfs(0);
return totalSum;
}
};
class Solution:
def goodSubtreeSum(self, vals: List[int], par: List[int]) -> int:
MOD = 10**9 + 7
n = len(vals)
# 构建邻接表
children = [[] for _ in range(n)]
for i in range(1, n):
children[par[i]].append(i)
# 获取数字的掩码
def get_mask(val):
mask = 0
while val > 0:
digit = val % 10
if mask & (1 << digit):
return -1 # 重复数字
mask |= (1 << digit)
val //= 10
return mask
masks = [get_mask(val) for val in vals]
total_sum = 0
# 树形DP
def dfs(u):
nonlocal total_sum
dp = {0: 0} # 空集
# 处理所有子节点
for v in children[u]:
child_dp = dfs(v)
new_dp = {}
# 合并当前状态和子节点状态
for mask1, sum1 in dp.items():
for mask2, sum2 in child_dp.items():
if mask1 & mask2 == 0: # 没有重叠
new_mask = mask1 | mask2
new_dp[new_mask] = max(new_dp.get(new_mask, 0), sum1 + sum2)
dp = new_dp
# 尝试加入当前节点
if masks[u] != -1:
new_dp = dp.copy()
for mask, sum_val in dp.items():
if mask & masks[u] == 0:
new_mask = mask | masks[u]
new_dp[new_mask] = max(new_dp.get(new_mask, 0), sum_val + vals[u])
dp = new_dp
# 计算当前子树的最大值
max_val = max(dp.values()) if dp else 0
total_sum = (total_sum + max_val) % MOD
return dp
dfs(0)
return total_sum
public class Solution {
private const int MOD = 1000000007;
public int GoodSubtreeSum(int[] vals, int[] par) {
int n = vals.Length;
// 构建邻接表
List<int>[] children = new List<int>[n];
for (int i = 0; i < n; i++) {
children[i] = new List<int>();
}
for (int i = 1; i < n; i++) {
children[par[i]].Add(i);
}
// 获取数字的掩码
int GetMask(int val) {
int mask = 0;
while (val > 0) {
int digit = val % 10;
if ((mask & (1 << digit)) != 0) return -1; // 重复数字
mask |= (1 << digit);
val /= 10;
}
return mask;
}
int[] masks = new int[n];
for (int i = 0; i < n; i++) {
masks[i] = GetMask(vals[i]);
}
long totalSum = 0;
// 树形DP
Dictionary<int, long> DFS(int u) {
var dp = new Dictionary<int, long> { [0] = 0 }; // 空集
// 处理所有子节点
foreach (int v in children[u]) {
var childDp = DFS(v);
var newDp = new Dictionary<int, long>();
// 合并当前状态和子节点状态
foreach (var kvp1 in dp) {
foreach (var kvp2 in childDp) {
int mask1 = kvp1.Key, mask2 = kvp2.Key;
long sum1 = kvp1.Value, sum2 = kvp2.Value;
if ((mask1 & mask2) == 0) { // 没有重叠
int newMask = mask1 | mask2;
if (!newDp.ContainsKey(newMask)) newDp[newMask] = 0;
newDp[newMask] = Math.Max(newDp[newMask], sum1 + sum2);
}
}
}
dp = newDp;
}
// 尝试加入当前节点
if (masks[u] != -1) {
var newDp = new Dictionary<int, long>(dp);
foreach (var kvp in dp) {
int mask = kvp.Key;
long sum = kvp.Value;
if ((mask & masks[u]) == 0) {
int newMask = mask | masks[u];
if (!newDp.ContainsKey(newMask)) newDp[newMask] = 0;
newDp[newMask] = Math.Max(newDp[newMask], sum + vals[u]);
}
}
dp = newDp;
}
// 计算当前子树的最大值
long maxVal = 0;
foreach (long sum in dp.Values) {
maxVal = Math.Max(maxVal, sum);
}
totalSum = (totalSum + maxVal) % MOD;
return dp;
}
DFS(0);
return (int)totalSum;
}
}
var goodSubtreeSum = function(vals, par) {
const MOD = 1000000007;
const n = vals.length;
// Build adjacency list
const children = Array.from({length: n}, () => []);
for (let i = 1; i < n; i++) {
children[par[i]].push(i);
}
// Get digit mask for a value
function getDigitMask(val) {
let mask = 0;
while (val > 0) {
mask |= (1 << (val % 10));
val = Math.floor(val / 10);
}
return mask;
}
// Check if two masks conflict (share common digits)
function hasConflict(mask1, mask2) {
return (mask1 & mask2) !== 0;
}
const maxScores = new Array(n);
function dfs(node) {
const nodeMask = getDigitMask(vals[node]);
const nodeVal = vals[node];
// Start with just this node
let states = new Map();
states.set(nodeMask, nodeVal);
// Process each child
for (const child of children[node]) {
const childMaxScore = dfs(child);
const childStates = childStates;
const newStates = new Map(states);
// Try to combine current states with child states
for (const [mask1, sum1] of states) {
for (const [mask2, sum2] of childStates) {
if (!hasConflict(mask1, mask2)) {
const newMask = mask1 | mask2;
const newSum = sum1 + sum2;
if (!newStates.has(newMask) || newStates.get(newMask) < newSum) {
newStates.set(newMask, newSum);
}
}
}
}
states = newStates;
}
// Find maximum score for this subtree
let maxScore = 0;
for (const sum of states.values()) {
maxScore = Math.max(maxScore, sum);
}
maxScores[node] = maxScore;
window.childStates = states;
return maxScore;
}
// Alternative approach using proper state passing
function solve(node) {
const nodeMask = getDigitMask(vals[node]);
const nodeVal = vals[node];
let allStates = new Map();
allStates.set(nodeMask, nodeVal);
for (const child of children[node]) {
const childResult = solve(child);
const childStates = childResult.states;
const newStates = new Map(allStates);
for (const [mask1, sum1] of allStates) {
for (const [mask2, sum2] of childStates) {
if (!hasConflict(mask1, mask2)) {
const newMask = mask1 | mask2;
const newSum = sum1 + sum2;
if (!newStates.has(newMask) || newStates.get(newMask) < newSum) {
newStates.set(newMask, newSum);
}
}
}
}
allStates = newStates;
}
let maxScore = 0;
for (const sum of allStates.values()) {
maxScore = Math.max(maxScore, sum);
}
maxScores[node] = maxScore;
return { states: allStates, maxScore };
}
solve(0);
let result = 0;
for (const score of maxScores) {
result = (result + score) % MOD;
}
return result;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |