首页 > 代码库 > 树形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 }
树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。