面条老师捡到一颗黑白相间的树，这颗树有 n n 个节点，其中 k k 个节点是黑色的。 面条老师觉得，现在的树配色实在是杂乱无章，于是面条老师决定使用他祖传的剪刀来对这颗树进行修剪，面条老师可以选择一个边的集合 e 1 , e 2 . . . , e k （ ∀ i ∈ [ 1.. k ] , j ∈ [ 1.. k ] e 1 ​ ,e 2 ​ ...,e k ​ （∀i∈[1..k],j∈[1..k], 如果 i ≠ j i  =j, 那么就有 e i ≠ e j ） e i ​  =e j ​ ）,然后将这些边全部用祖传剪刀剪掉。可以预料到的是，树会分裂成 k + 1 k+1 个小树。面条老师希望这 k + 1 k+1 个小树都恰好有一个黑色节点。 面条老师在准备开始剪之前突然想到一个问题：有多少种不同的边的集合可以让修剪后的 k + 1 k+1 个小树都恰好有一个黑色节点呢？ 面条老师修剪树是一把好手，可是在思考问题上却遇到了很大的困难。你作为面条老师的好朋友，你能告诉他这个不同的边的集合的数量是多少么？ 输入描述 第一行是一个

这是一个树形动态规划问题。我们需要计算有多少种方式删除一些边，使得每个连通块恰好有一个黑色节点。 ## 问题分析 给定一棵树，有 $n$ 个节点，其中 $k$ 个是黑色节点。我们需要删除一些边，使得剩下的每个连通块恰好有一个黑色节点。 关键观察： - 如果某个子树包含 0 个黑色节点，那么它必须与父节点所在的连通块合并。 - 如果某个子树包含 1 个黑色节点，那么它可以独立成为一个连通块（即切断它与父节点的边）。 - 如果某个子树包含超过 1 个黑色节点，那么它不能独立，必须与父节点连通。 ## 动态规划状态 定义 `dp[u][0]` 和 `dp[u][1]`： - `dp[u][0]`：以节点 u 为根的子树，不包含黑色节点时，满足条件的方案数。 - `dp[u][1]`：以节点 u 为根的子树，恰好包含一个黑色节点时，满足条件的方案数。 转移规则： 1. 如果节点 u 是黑色： - `dp[u][1]` 初始为 1（只包含 u 自己）。 - 对于每个子节点 v： - 如果保留边 (u, v)，那么 v 的子树必须贡献 0 个黑色节点（即 `dp[v][0]`）。 - 如果切断边 (u, v)，那么 v 的子树必须恰好有 1 个黑色节点（即 `dp[v][1]`）。 - 所以 `dp[u][1] = product_{v in children(u)} (dp[v][0] + dp[v][1])`。 2. 如果节点 u 是白色： - `dp[u][0]` 初始为 1（只包含 u 自己，没有黑色节点）。 - `dp[u][1]` 初始为 0。 - 对于每个子节点 v： - 如果保留边 (u, v)，那么 v 的子树贡献可以合并到 u 的子树中。 - 如果切断边 (u, v)，那么 v 的子树必须恰好有 1 个黑色节点。 - 具体转移： - 新的 `dp[u][0] = dp[u][0] * (dp[v][0] + dp[v][1])`。 - 新的 `dp[u][1] = dp[u][1] * (dp[v][0] + dp[v][1]) + dp[u][0] * dp[v][1]`。 最终答案： 根节点的 `dp[root][1]` 就是答案，因为整棵树必须恰好有 1 个黑色节点（实际上整棵树有 k 个黑色节点，但通过切断边，每个连通块恰好一个黑色节点，所以根所在的连通块也恰好一个黑色节点）。 ## 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MOD = 1e9 + 7; vector<vector<int>> adj; vector<int> color; vector<vector<long long>> dp; void dfs(int u, int parent) { if (color[u] == 1) { // 黑色节点 dp[u][1] = 1; for (int v : adj[u]) { if (v == parent) continue; dfs(v, u); dp[u][1] = dp[u][1] * ((dp[v][0] + dp[v][1]) % MOD) % MOD; } } else { // 白色节点 dp[u][0] = 1; for (int v : adj[u]) { if (v == parent) continue; dfs(v, u); long long sum_v = (dp[v][0] + dp[v][1]) % MOD; long long new_dp0 = dp[u][0] * sum_v % MOD; long long new_dp1 = (dp[u][1] * sum_v % MOD + dp[u][0] * dp[v][1] % MOD) % MOD; dp[u][0] = new_dp0; dp[u][1] = new_dp1; } } } int main() { int n; cin >> n; // 读取树结构 vector<int> parent(n-1); for (int i = 0; i < n-1; i++) { cin >> parent[i]; } // 构建邻接表 adj.resize(n); for (int i = 0; i < n-1; i++) { int u = i + 1; int v = parent[i]; adj[u].push_back(v); adj[v].push_back(u); } // 读取颜色 color.resize(n); for (int i = 0; i < n; i++) { cin >> color[i]; } // 初始化DP数组 dp.assign(n, vector<long long>(2, 0)); // 从节点0开始DFS dfs(0, -1); // 输出结果 cout << dp[0][1] % MOD << endl; return 0; } ``` ## 算法复杂度 - 时间复杂度：O(n)，每个节点访问一次。 - 空间复杂度：O(n)，用于存储树和DP状态。 ## 示例解释 对于输入： ``` 3 0 0 1 0 1 ``` 表示： - 3个节点 - 边：(1,0), (2,0) - 颜色：节点0黑色，节点1白色，节点2黑色 可能的方案： 1. 不删除任何边：连通块包含2个黑色节点，不符合条件。 2. 删除边(1,0)：得到两个连通块：{0,2}（2个黑色节点）和{1}（0个黑色节点），不符合条件。 3. 删除边(2,0)：得到两个连通块：{0,1}（1个黑色节点）和{2}（1个黑色节点），符合条件。 4. 删除两条边：得到三个连通块：{0}（1个黑色节点）、{1}（0个黑色节点）、{2}（1个黑色节点），不符合条件。 只有方案3符合条件，所以答案是1。 这个算法可以正确处理所有情况，包括多个黑色节点的复杂树结构。 [2026-01-20 19:14:45 | AI问答 | 1421点数解答]