題意

傳送門 Codeforces 461B Appleman and Tree

題解

$d{p}_{v,k}$ 代表以節點 $v$ 為根的子樹中，包含了 $v$ 的聯通分量是否存在一個黑色節點 ，同時其余聯通分量僅包含一個黑色節點情況下，劃分方案的數量。DFS 求解，對于每一條連向子節點的邊，考慮是否刪去這條邊，進行狀態轉移即可。總時間復雜度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 1e9 + 7;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<vector<int>> g(n);for (int i = 0; i < n - 1; ++i) {int p;cin >> p;g[p].push_back(i + 1);}vector<int> x(n);for (int i = 0; i < n; ++i) {cin >> x[i];}vector<vector<int>> dp(n, vector<int>(2));function<void(int)> dfs = [&](int v) {dp[v][x[v]] = 1;for (int u : g[v]) {dfs(u);auto tmp = dp[v];dp[v][0] = dp[v][1] = 0;for (int k = 0; k < 2; ++k) {(dp[v][k] += (ll)tmp[k] * dp[u][1] % MOD) %= MOD;}for (int k = 0; k < 2; ++k) {(dp[v][k] += (ll)tmp[k] * dp[u][0] % MOD) %= MOD;}(dp[v][1] += (ll)tmp[0] * dp[u][1] % MOD) %= MOD;}};dfs(0);cout << dp[0][1] << '\n';return 0;
}