首页 > 代码库 > Codeforces Round #263 (Div. 2) D. Appleman and Tree 树形dp
Codeforces Round #263 (Div. 2) D. Appleman and Tree 树形dp
链接：
http://codeforces.com/contest/462/problem/D
题意：
给定n个点的树，
0为根，下面n-1行表示每个点的父节点
最后一行n个数 表示每个点的颜色，0为白色，1为黑色。
把树分成若干个联通块使得每个联通块有且仅有一个黑点，问有多少种分法（结果mod1e9+7）
题解：
树形dp，每个点有2个状态，已经归属于某个黑点和未归属于某个黑点。
代码：
31 int n;32 int x[MAXN];33 VI G[MAXN];34 ll dp[MAXN][2];35 36 void dfs(int u) {37 if (x[u]) dp[u][1] = 1;38 else dp[u][0] = 1;39 rep(i, 0, G[u].size()) {40 int v = G[u][i];41 dfs(v);42 ll old[2] = { dp[u][0], dp[u][1] };43 dp[u][0] = (old[0] * dp[v][1] + old[0] * dp[v][0]) % MOD;44 dp[u][1] = (old[1] * dp[v][1] + old[1] * dp[v][0] + old[0] * dp[v][1]) % MOD;45 }46 }47 48 int main() {49 ios::sync_with_stdio(false), cin.tie(0);50 cin >> n;51 rep(i, 1, n) {52 int p;53 cin >> p;54 G[p].pb(i);55 }56 rep(i, 0, n) cin >> x[i];57 dfs(0);58 cout << dp[0][1] << endl;59 return 0;60 }
Codeforces Round #263 (Div. 2) D. Appleman and Tree 树形dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。