本文共 1611 字,大约阅读时间需要 5 分钟。
给出一棵树,每个点是白色或者黑色,问有多少种方案能够通过去掉一些边使每个联通块中只有一个黑色的点。
#include#include #include #include #include #define MAX 100007using namespace std;typedef long long LL;LL dp[MAX][2];int c[MAX],n;vector e[MAX];const LL mod = 1e9+7;void Clear(){ for ( int i = 0 ; i < MAX ; i++ ) e[i].clear(); memset ( dp , 0 , sizeof ( dp ));}void add ( int u , int v ){ e[u].push_back ( v ); e[v].push_back ( u );}void dfs ( int u , int p ){ dp[u][c[u]] = 1; for ( int i = 0 ; i < e[u].size() ; i++ ) { int v = e[u][i]; if ( v == p ) continue; dfs ( v , u ); LL old[]={dp[u][0],dp[u][1]}; dp[u][1] = old[1]*dp[v][0]%mod + old[0]*dp[v][1]%mod+ old[1]*dp[v][1]%mod; dp[u][1] %= mod; dp[u][0] = old[0]*dp[v][0]%mod + old[0]*dp[v][1]%mod; dp[u][0] %= mod; }}int main ( ){ while ( ~scanf ( "%d" , &n )) { Clear(); for ( int i = 1 ; i < n ; i++ ) { int x; scanf ( "%d" , &x ); add ( i , x ); } for ( int i = 0 ; i < n ; i++ ) scanf ( "%d" , &c[i] ); dfs ( 0 , -1 ); printf ( "%I64d\n" , dp[0][1] ); }}
转载地址:http://vqvjn.baihongyu.com/