首页 > 代码库 > 树形DP

树形DP

 

Appleman and Tree

 CodeForces - 461B 

题意:

题解:http://blog.csdn.net/u011580493/article/details/39032195

技术分享
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long  long
 4 const int mod=1000000007;
 5 const int maxv=1e5+10;
 6 int b[maxv];
 7 struct Edge{
 8     int v,nex;
 9 }e[maxv<<1];
10 int head[maxv];
11 int cnt=0;
12 void init(){
13     memset(head,-1,sizeof(head));
14     cnt=0;
15 }
16 void add(int u,int v){
17     e[cnt].v=v;
18     e[cnt].nex=head[u];
19     head[u]=cnt++;
20 }
21 ll dp[maxv][2];
22 void dfs(int u,int f){
23     if(b[u]) dp[u][1]=1;
24     else dp[u][0]=1;
25     for(int i=head[u];~i;i=e[i].nex){
26         int v=e[i].v;
27         if(v==f) continue;
28         dfs(v,u);
29         dp[u][1]=(dp[u][1]*dp[v][0]+dp[u][1]*dp[v][1]+dp[u][0]*dp[v][1])%mod;
30         dp[u][0]=(dp[u][0]*dp[v][0]+dp[u][0]*dp[v][1])%mod;
31     }
32 }
33 int main(){
34     int n;
35     scanf("%d",&n);
36     int u;
37     init();
38     for(int i=1;i<n;i++){
39         scanf("%d",&u);
40         add(u,i);
41         add(i,u);
42     }
43     for(int i=0;i<n;i++){
44         scanf("%d",&b[i]);
45     }
46     dfs(0,-1);
47     printf("%lld\n",dp[0][1]);
48 }
View Code

 

树形DP