企业官网建设流程全解析

这是 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)。

```typescript
function 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 递归通常安全）。