本文主要是介绍Codeforces Round #263 (Div. 1) B. Appleman and Tree( 树形DP )，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目: LINK
给定一个树，每个节点是白色或者黑色。可以删去一个边的集合使得剩下来的每个树里面有且仅有一个节点是黑色的。求这样集合的数量。
显然是树形DP。 dp[n][2]， dp[i][j]代表到i这个点它所在的子树的划分情况都满足条件(每部分只有一个黑点)的情况，dp[i][0] 包含i节点的这部分没有黑点的集合数量，dp[i][1]表示这部分有一个黑点的集合数量。
对于每个节点，计算到它的一个子树(根节点v) (设连接的边为x)的时候，dp[i][0] 为dp[i][0] * dp[v][1] + dp[i][0] * dp[v][0], 已处理完的一定要取dp[i][0], 如果取x 则子树取dp[v][0],如果不取x, 则子树取dp[v][1].
dp[i][1] 为 dp[i][1] *(dp[v][0] + dp[v][1]) + dp[i][0] *dp[v][1] , 如果处理完的取dp[i][1],x取的话为dp[v][0], 不取的话为dp[v][1]; 如果处理完的取dp[i][0], x一定要取且要乘以dp[v][1] (ps: dp[v][0] 不能要，如果要的话 v 点的部分会出现不含黑点的情况)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define INF 1000000000
typedef __int64 LL;
#define N 111111
#define mod 1000000007
vector< LL > ee[N];
LL n, col[N], dp[N][3];
void dfs(LL v, LL p)
{dp[v][1]= dp[v][0] = 0;dp[v][col[v]] = 1;for(int i = 0; i<ee[v].size(); i++) {int vv = ee[v][i];if(vv == p) continue;dfs(vv, v);LL _0 = dp[v][0], _1 = dp[v][1];dp[v][0] = ( _0 * dp[vv][0] % mod + _0 * dp[vv][1] % mod) % mod;dp[v][1] = ( _1 * (dp[vv][0] + dp[vv][1]) %mod + _0 * dp[vv][1] %mod) %mod;}
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEscanf("%I64d", &n);LL tmp;for(int i = 1; i<n; i++) {scanf("%I64d", &tmp);ee[i].push_back(tmp);ee[tmp].push_back(i);}for(int i= 0; i<n; i++) {scanf("%I64d", &tmp); col[i] = tmp;}dfs(0, -1);printf("%I64d\n",dp[0][1]);return 0;
}这篇关于Codeforces Round #263 (Div. 1) B. Appleman and Tree( 树形DP )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
