1. 算法核心：树形 DP

这道题是典型的树形背包 DP（Tree DP with Knapsack）。 我们需要在树上选 $k$ 个点放置监听设备，要求覆盖所有点。

状态定义

为了描述当前节点 $u$ 的状态，我们需要知道：

1. $u$ 是否放了设备：因为这决定了 $u$ 的父节点和子节点是否被覆盖。
2. $u$ 是否被覆盖：
   • 如果 $u$ 放了设备，它自己没被覆盖（设备不监听自己），需要父节点或子节点来覆盖它。
   • 如果 $u$ 没放设备，它可能已经被子节点覆盖，或者还需要父节点来覆盖。

因此，定义状态 $f[u][i][x][y]$：

• $u$：当前节点。
• $i$：以 $u$ 为根的子树中，一共放置了 $i$ 个设备。
• $x$（$0/1$）：$u$ 是否被子树中的节点覆盖。
  • $0$：$u$ 还没被子树覆盖（如果不被父节点覆盖，目前是不合法的）。
  • $1$：$u$ 已经被子树覆盖了（已经是合法的，父节点放不放无所谓）。
• $y$（$0/1$）：$u$ 本身是否放置了设备。
  • $0$：没有放置。
  • $1$：放置了。

具体状态含义：

• $f[u][i][0][0]$：$u$ 无设备，且未被子树覆盖（需要父节点覆盖）。
• $f[u][i][1][0]$：$u$ 无设备，已被子树覆盖（安全）。
• $f[u][i][0][1]$：$u$ 有设备，且未被子树覆盖（需要父节点覆盖）。
• $f[u][i][1][1]$：$u$ 有设备，已被子树覆盖（安全）。

---

2. 状态转移逻辑

这份代码使用了一种容斥/差分的技巧来简化状态转移方程，特别是针对 $x=1$（已被覆盖）的情况。

我们逐个分析代码中的 g 数组（临时数组，用于合并子树 $v$ 到 $u$）：

1. 目标：$u$ 无设备，未被覆盖 ($0, 0$)

• $u$ 既然没被覆盖，说明它之前的子树没覆盖它，当前的子节点 $v$ 也不能覆盖它（即 $v$ 不能有设备）。
• 同时，$u$ 也没有设备，所以 $u$ 无法覆盖 $v$。因此 $v$ 必须自己解决自己的覆盖问题（即 $v$ 必须是已被覆盖的状态）。
• 转移：$f[u][\dots][0][0] \times f[v][\dots][1][0]$
  • $v$ 状态必须是 $1,0$（$v$ 被孙子覆盖，且 $v$ 无设备）。

2. 目标：$u$ 有设备，未被覆盖 ($0, 1$)

• $u$ 有设备，所以 $u$ 可以覆盖 $v$。因此 $v$ 不需要被它的子树覆盖（$v$ 的 $x$ 可以是 $0$ 或 $1$）。
• 但是 $u$ 未被覆盖，说明 $v$ 不能有设备（否则 $v$ 会覆盖 $u$）。
• 转移：$f[u][\dots][0][1] \times (f[v][\dots][0][0] + f[v][\dots][1][0])$

3. 目标：$u$ 无设备，已被覆盖 ($1, 0$)

• 这里代码使用了技巧。直接计算“$u$ 被覆盖”的情况比较复杂（因为可能是之前的子树覆盖的，也可能是当前 $v$ 覆盖的）。
• 代码逻辑：先计算一个宽泛的中间状态，再减去不合法的情况。
• 中间计算：$f[u][\dots][1][0]$ (初始化为1) $\times (f[v][\dots][1][0] + f[v][\dots][1][1])$
  • 这里的意思是：只要 $v$ 是安全的（被覆盖的），我们就把方案加进去。此时 $u$ 可能是被之前的子树覆盖，也可能没被覆盖。
• 去重/修正：循环结束后，执行 f[u][i][1][0] -= f[u][i][0][0]。
  • 总方案（忽略 $u$ 是否被覆盖） - $u$ 未被覆盖的方案 = $u$ 确信被覆盖的方案。

4. 目标：$u$ 有设备，已被覆盖 ($1, 1$)

• 中间计算：$f[u][\dots][1][1]$ (初始化为1) $\times$ ($v$ 的所有状态和)
  • 因为 $u$ 有设备，$v$ 被 $u$ 覆盖，所以 $v$ 无论原本是否被覆盖都是合法的。
  • 这里的中间状态表示：$u$ 有设备，且 $v$ 合法的所有组合（此时 $u$ 可能被子树覆盖，也可能没被覆盖）。
• 去重/修正：循环结束后，执行 f[u][i][1][1] -= f[u][i][0][1]。
  • 总方案 - $u$ 未被覆盖的方案 = $u$ 确信被覆盖的方案。

---

3. 代码细节解析

void dfs(int u, int p) {
    // 初始化
    // 注意：这里把 x=1 的状态也初始化为 1，是为了配合后面的容斥计算
    // 可以理解为刚开始“假设”所有情况都存在，最后减去不满足 x=1 的情况
    f[u][0][0][0] = 1; // 0设备，未覆盖，无设备
    f[u][1][0][1] = 1; // 1设备，未覆盖，有设备
    f[u][0][1][0] = 1; // 用于容斥的基底
    f[u][1][1][1] = 1; // 用于容斥的基底
    sz[u] = 1;

    for (int v : eg[u])
        if (v != p) {
            dfs(v, u);
            static LL g[N][2][2]; // 临时数组存储合并结果
            // 清空 g ...
            
            // 树形背包合并
            // min(k, sz[u]) 和 min(k-i, sz[v]) 是复杂度优化的关键
            // 保证复杂度为 O(nk) 而不是 O(nk^2)
            fr(i, 0, min(k, sz[u])) {
                fr(j, 0, min(k - i, sz[v])) {
                    // 转移方程如上文分析
                    // 1. u 没设备，没被覆盖：只能接纳 v 没设备且 v 自保的情况
                    g[i + j][0][0] = (g[i + j][0][0] + 1LL * f[u][i][0][0] * f[v][j][1][0]) % mod;
                    
                    // 2. u 有设备，没被覆盖：接纳 v 没设备 (v 是否自保无所谓，u保它)
                    g[i + j][0][1] = (g[i + j][0][1] + 1LL * f[u][i][0][1] * ((LL)f[v][j][0][0] + f[v][j][1][0])) % mod;
                    
                    // 3. u 没设备，宽泛状态：只要 v 自保即可 (v 有无设备均可)
                    g[i + j][1][0] = (g[i + j][1][0] + 1LL * f[u][i][1][0] * ((LL)f[v][j][1][0] + f[v][j][1][1])) % mod;
                    
                    // 4. u 有设备，宽泛状态：v 只要合法即可 (u保它，或者它有设备，或者它自保)
                    // v 的所有 4 种状态相加
                    g[i + j][1][1] = (g[i + j][1][1] + 1LL * f[u][i][1][1] * ((LL)f[v][j][0][0] + f[v][j][0][1] + f[v][j][1][0] + f[v][j][1][1])) % mod;
                }
            }
            sz[u] += sz[v];
            // 将 g 复制回 f
            fr(i, 0, k) fr(x, 0, 1) fr(y, 0, 1) f[u][i][x][y] = g[i][x][y];
        }

    // 容斥处理：得到真正的 x=1 (被子树覆盖) 的状态
    fr(i, 0, k) {
        f[u][i][1][0] = (f[u][i][1][0] - f[u][i][0][0] + mod) % mod;
        f[u][i][1][1] = (f[u][i][1][1] - f[u][i][0][1] + mod) % mod;
    }
}

4. 复杂度分析

• 时间复杂度：虽然看起来有三层循环（$u$, $i$, $j$），但由于背包容量上限是 $k$，且在循环中使用了 sz[u] 和 sz[v] 进行限制（上下界优化），树形背包的经典复杂度证明指出，对于合并大小为 $S_u$ 和 $S_v$ 的子树，代价是 $O(S_u \cdot S_v)$。全局总代价是 $O(n \cdot k)$。
  • 数据范围 $n=10^5, k=100$，计算量约为 $10^7$ 级别，可以通过。
• 空间复杂度：$O(nk)$，用于存储 DP 数组。

5. 最终答案

答案是根节点 $1$ 在放了 $k$ 个设备后，被覆盖的方案数。 注意：根节点没有父节点，所以它必须被子树覆盖（状态 $1, 0$ 或 $1, 1$）。

$$Ans = (f[1][k][1][0] + f[1][k][1][1]) \pmod{10^9+7} $$