CF461B Appleman and Tree 的题解

· · 题解

考察：树形 DP。

状态挺神奇的。

考虑设 f_{u,0/1} 在以 u 为根的子树中，点 u 在没有黑点的连通块内或有且仅有一个黑点的联通块内的方案数。

那么在合并儿子节点时，设 v 是 u 的儿子节点，有方程：

\begin{cases} f_{u,1} &\larr f_{u,1} \times f_{v,0} + f_{u,1} \times f_{v,1} + f_{u,0} \times f_{v,1}\\ f_{u,0} &\larr f_{u,0} \times f_{v,0} + f_{u,0} \times f_{v,1} \end{cases}

初始化为 f_{u,col_u} = 1。

实质上就是枚举了 u,v 之间的边的联通情况对答案的影响。

状态清奇，好思路。

::::success[code]

#include<bits/stdc++.h>
#define endl '\n'
//#define MSOD

using namespace std;
using ll = long long;
constexpr ll N = 1e5 + 5, M = 1e9 + 7;

ll n;
ll dp[N][2];
bool col[N];
vector<ll> g[N];
inline void dfs(ll u, ll dad) {
    for(auto v : g[u]) {
        if(v == dad) {
            continue;
        }
        dfs(v, u);
        dp[u][1] = dp[u][1] * dp[v][0] % M + dp[u][1] * dp[v][1] % M + dp[u][0] * dp[v][1] % M;
        dp[u][0] = dp[u][0] * dp[v][0] % M + dp[u][0] * dp[v][1] % M;
        dp[u][1] %= M, dp[u][0] %= M;
    }
    return;
}
inline void solve() {
    cin>>n;
    for(int i = 0 ; i < n - 1 ; i ++) {
        ll x;
        cin>>x;
        g[x].push_back(i + 1), g[i + 1].push_back(x); 
    }
    for(int i = 0 ; i < n ; i ++) {
        cin>>col[i];
        dp[i][col[i]] = 1;
    }
    dfs(0, -1);
    cout<<dp[0][1];
    return;
}

signed main() {
    ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
    int TC = 1;
#ifdef MSOD
    cin>>TC;
#endif
    while(TC --) {
        solve();
    }
    return 0;
}

::::