CF461B Appleman and Tree （树DP）

CF462D

Codeforces Round #263 (Div. 2) D

Codeforces Round #263 (Div. 1) B

B. Appleman and Tree time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 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 p0, p1, ..., pn - 2 (0 ≤ pi ≤ i). Where pi means that there is an edge connecting vertex (i + 1) of the tree and vertex pi. Consider tree vertices are numbered from 0 to n - 1. The third line contains the description of the colors of the vertices: n integers x0, x1, ..., xn - 1 (xi is either 0 or 1). If xi 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). Sample test(s) 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

题意：有n个结点的树，结点编号0~n-1，0为根，分别给出1~n-1的父亲，再给出0~n-1各个结点的颜色（0为白，1为黑），要将其中一些边切掉，使每个联通块有且只有1个黑点，求切法种类数。

题解：树形DP。

从根DFS，f[x][0]表示对{x点和它的子树、x点连接父亲结点的边}这一整坨，有多少种方案使得x这个联通块没黑点（x是黑点的时候这个也不为0，是把x的父边切掉的种类数）

f[x][1]是这个联通块有黑点的种类数。

太难了！怪不得大家都掉分飞起，虽然题解的代码看起来很短，我根本想不出来啊看了半天还是不懂啊！

具体还是看代码吧，写了点注释，这个统计方法太碉了，我也弄得不是很清楚，算了日后再说。

代码：

 //#pragma comment(linker, "/STACK:102400000,102400000")
 #include<cstdio>
 #include<cmath>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 #include<cmath>
 #include<map>
 #include<set>
 #include<stack>
 #include<queue>
 using namespace std;
 #define ll long long
 #define usll unsigned ll
 #define mz(array) memset(array, 0, sizeof(array))
 #define minf(array) memset(array, 0x3f, sizeof(array))
 #define REP(i,n) for(i=0;i<(n);i++)
 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
 #define RD(x) scanf("%d",&x)
 #define RD2(x,y) scanf("%d%d",&x,&y)
 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
 #define WN(x) printf("%d\n",x);
 #define RE  freopen("D.in","r",stdin)
 #define WE  freopen("1biao.out","w",stdout)
 #define mp make_pair
 #define pb push_back

 const int maxn=;
 const int MOD=1e9+;

 int n;
 int a[maxn];

 struct Edge {
     int next,v;
 } e[*maxn];
 int en=;
 int head[maxn];

 void add(int x,int y) {
     e[en].v=y;
     e[en].next=head[x];
     head[x]=en++;
 }

 bool u[maxn];
 ll f[maxn][];///f[x][j] j=1表示x所在联通块有黑点，0表示无黑店 的种类数，包括x连接父亲的边和子树所有的边
 void dfs(int x){
     //printf("[in %d]",x);
     int i;
     u[x]=;
     f[x][]=;
     f[x][]=;///先假设当前点是个白点
     for(i=head[x]; i!=-; i=e[i].next) {
         if(!u[e[i].v]) {
             dfs(e[i].v);
             f[x][]=(f[x][]*f[e[i].v][] + f[x][]*f[e[i].v][])%MOD;///有黑点的情况，先用已经统计的有黑点的情况乘一发儿子没黑点的情况，然后用已经统计的没黑点的情况乘一发儿子有黑点的情况
             f[x][]=f[x][]*f[e[i].v][]%MOD;///没黑点的情况直接乘儿子没黑点的情况
         }
     }
     u[x]=;
     ///下面是对x点的父边的处理
     if(a[x]==)f[x][]=(f[x][]+f[x][])%MOD;///x是白点，儿子要是有黑点，砍了x的父边就是没黑点，所以没黑点（f[x][0]）的情况要加上有黑点的情况（f[x][1]）
     else f[x][]=f[x][];///x点是黑点，那不砍父边的情况（f[x][1]）只有让x的儿子都不黑，砍父边的情况（f[x][0]）也是x的儿子都不黑，因为x自己黑嘛，儿子再黑就连到一起了
     //printf("[out %d,flag=%d,re=%I64d,a[x]=%d]\n",x,flag,re,a[x]);
 }

 ll farm() {
     if(n==)return ;
     mz(u);
     dfs();
     return f[][];
 }

 int main() {
     int i;
     int x;
     RD(n);
     memset(head,-,sizeof(head));
     en=;
     REP(i,n-) {
         scanf("%d",&x);
         add(i+,x);
         add(x,i+);
     }
     for(i=; i<n; i++)
         scanf("%d",&a[i]);
     printf("%I64d",farm());
     return ;
 }