Appleman has a tree with n vertices. Some of the vertices (at least one) are colored black and other vertices are colored white.

Consider a set consisting of k (0?≤?k?<?n) edges of Appleman’s tree. If Appleman deletes these edges from the tree, then it will split into (k?+?1) parts. Note, that each part will be a tree with colored vertices.

Now Appleman wonders, what is the number of sets splitting the tree in such a way that each resulting part will have exactly one black vertex? Find this number modulo 1000000007 (109?+?7).

Input
The first line contains an integer n (2??≤?n?≤?105) — the number of tree vertices.

The second line contains the description of the tree: n?-?1 integers p 0,?p 1,?…,?p n?-?2 (0?≤?p i?≤?i). Where p i means that there is an edge connecting vertex (i?+?1) of the tree and vertex p i. Consider tree vertices are numbered from 0 to n?-?1.

The third line contains the description of the colors of the vertices: n integers x 0,?x 1,?…,?x n?-?1 ( x i is either 0 or 1). If x i is equal to 1, vertex i is colored black. Otherwise, vertex i is colored white.

Output
Output a single integer — the number of ways to split the tree modulo 1000000007 (109?+?7).

Examples
Input
3
0 0
0 1 1
Output
2
Input
6
0 1 1 0 4
1 1 0 0 1 0
Output
1
Input
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
Output
27
dp數組的每一種狀態代表著什么，并且每一種狀態之間如何轉換是解決dp問題的關鍵之處。
思路：
dp[i][0]代表著以i為父節點的樹，沒有黑點的狀態數目。
dp[i][1]代表著以i為父節點的數，有1個黑點的狀態數目。
狀態轉移方程：
①如果當前節點是黑色，父親節點也是黑色，那么只能斷開，只對dp[u][1]有貢獻。
②如果當前節點是黑色，父親節點是白色，可以與父親節點合并，也可以與父親節點斷開，對dp[u][0]和dp[u][1]同時有貢獻。
③如果當前節點是白色，父節點是黑色，只能合并，對dp[u][1]有貢獻。
④如果當前節點是白色，父親節點是白色，只能合并，對dp[u][0]有貢獻。
最終輸出dp[0][1]就可以。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std;const int maxx=1e5+100; struct edge{int to,next; }e[maxx<<1]; ll dp[maxx][2]; int head[maxx<<1]; int col[maxx]; int n,tot;inline void init() {memset(head,-1,sizeof(head));tot=0; } inline void add(int u,int v) {e[tot].next=head[u],e[tot].to=v,head[u]=tot++; } inline void dfs(int u,int f) {if(col[u]) dp[u][1]=1,dp[u][0]=0;else dp[u][0]=1,dp[u][1]=0;for(int i=head[u];i!=-1;i=e[i].next){int to=e[i].to;if(to==f) continue;dfs(to,u);ll t1=dp[u][1],t0=dp[u][0];dp[u][1]=(t1*dp[to][0])%mod+(t0*dp[to][1])%mod+(t1*dp[to][1])%mod;dp[u][0]=(t0*dp[to][1])%mod+(t0*dp[to][0])%mod;dp[u][1]%=mod;dp[u][0]%=mod;} } int main() {scanf("%d",&n);init();int x;for(int i=1;i<n;i++){scanf("%d",&x);add(i,x);add(x,i);}for(int i=0;i<n;i++) scanf("%d",&col[i]);dfs(0,-1);printf("%d\n",dp[0][1]);return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Appleman and Tree CodeForces - 461B（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。