codeforces 461B Appleman and Tree

浏览数：29 / 时间：2015年06月11日

题意：问你将含有黑白点的无向树使得每个子树中只有一个黑点的方法数。

解题思路:树形dp，dp[i][0/1] 表示第i 个节点的联通图中是否有 1个黑点的种类数。

解题代码：

 1 // File Name: 461c.cpp
 2 // Author: darkdream
 3 // Created Time: 2015年03月11日 星期三 10时53分22秒
 4 
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 #define M 1000000007
26 using namespace std;
27 int color[100005];
28 LL dp[100005][2];
29 int n; 
30 vector<int> mp[100005]; 
31 int dfs(int k ,int la)
32 {
33      if(color[k])
34         dp[k][1] = 1; 
35      dp[k][0] = dp[k][1]^1;
36      for(int i = 0 ;i < mp[k].size(); i ++)
37      {
38          if(mp[k][i] == la ) 
39              continue;
40          int y = mp[k][i];
41          dfs(y,k);
42          LL t1 = dp[k][0] *(dp[y][0]+dp[y][1]) ;
43          LL t2 = dp[k][1] *(dp[y][0] + dp[y][1]) + dp[k][0]*dp[y][1];
44          dp[k][0] = t1 % M; 
45          dp[k][1] = t2 % M;
46          
47      }
48      
49 }
50 int main(){
51       scanf("%d",&n);
52       for(int i = 0;i < n - 1;i ++)
53       {
54          int p ; 
55          scanf("%d",&p);
56          mp[p].push_back(i+1);
57          mp[i+1].push_back(p);
58       }
59       for(int i = 0 ;i < n;i ++)
60       {
61          scanf("%d",&color[i]);
62       }
63       dfs(0,0);
64       printf("%I64d\n",dp[0][1]);    
65 return 0;
66 }