这是 LeetCode 3939 统计有根树中不相邻子集的数目 的 TypeScript 实现。解题思路这是一道树形 DP 问题。对于每个节点我们需要维护两种状态和对 k 取模- dp0[mod]当前节点不选子树中已选节点和模 k 为 mod 的方案数- dp1[mod]当前节点选子树中已选节点和模 k 为 mod 的方案数状态转移- 当前节点不选子节点可选可不选dp0 与 (cdp0 cdp1) 做背包合并- 当前节点选子节点必须不选dp1 只与 cdp0 做背包合并初始状态- dp0[0] 1不选当前节点空集- dp1[nums[u] % k] 1只选当前节点答案 dp0[0] dp1[0] - 1减去全局空集时间复杂度 O(n \cdot k^2)空间复杂度 O(n \cdot k)。typescriptfunction countValidSubsets(parent: number[], nums: number[], k: number): number {const MOD 1_000_000_007;const n parent.length;// 建树const children: number[][] Array.from({ length: n }, () []);for (let i 1; i n; i) {children[parent[i]].push(i);}// 预先对节点值取模const vals nums.map(x ((x % k) k) % k);// 安全乘法取模避免 JS Number 精度溢出const mul (a: number, b: number): number {return Number((BigInt(a) * BigInt(b)) % BigInt(MOD));};// DFS 返回 [dp0, dp1]function dfs(u: number): [number[], number[]] {const dp0: number[] new Array(k).fill(0); // u 不选const dp1: number[] new Array(k).fill(0); // u 选dp0[0] 1;dp1[vals[u]] 1;for (const v of children[u]) {const [cdp0, cdp1] dfs(v);const ndp0: number[] new Array(k).fill(0);const ndp1: number[] new Array(k).fill(0);// u 不选v 可选可不选for (let i 0; i k; i) {if (dp0[i] 0) continue;for (let j 0; j k; j) {if (cdp0[j]) {const idx (i j) % k;ndp0[idx] (ndp0[idx] mul(dp0[i], cdp0[j])) % MOD;}if (cdp1[j]) {const idx (i j) % k;ndp0[idx] (ndp0[idx] mul(dp0[i], cdp1[j])) % MOD;}}}// u 选v 必须不选for (let i 0; i k; i) {if (dp1[i] 0) continue;for (let j 0; j k; j) {if (cdp0[j]) {const idx (i j) % k;ndp1[idx] (ndp1[idx] mul(dp1[i], cdp0[j])) % MOD;}}}for (let i 0; i k; i) {dp0[i] ndp0[i];dp1[i] ndp1[i];}}return [dp0, dp1];}const [dp0, dp1] dfs(0);let ans dp0[0] dp1[0] - 1; // 减去空集ans % MOD;if (ans 0) ans MOD;return ans;}说明- 使用 BigInt 进行中间乘法运算避免 JavaScript Number 类型在 10^{18} 级别乘积时的精度丢失问题。- 由于 parent[i] i也可以按逆序迭代实现非递归版本避免栈深度问题n \le 1000 递归通常安全。