CF462D
Codeforces Round #263 (Div. 2) D
Codeforces Round #263 (Div. 1) B
|
B. Appleman and Tree
time limit per test
2 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputAppleman 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 Output
2 Input
6 Output
1 Input
10 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]是这个联通块有黑点的种类数。
太难了！怪不得大家都掉分飞起，虽然题解的代码看起来很短，我根本想不出来啊看了半天还是不懂啊！
具体还是看代码吧，写了点注释，这个统计方法太碉了，我也弄得不是很清楚，算了日后再说。
代码：
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12 using namespace std; 13 #define ll long long 14 #define usll unsigned ll 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define minf(array) memset(array, 0x3f, sizeof(array)) 17 #define REP(i,n) for(i=0;i<(n);i++) 18 #define FOR(i,x,n) for(i=(x);i<=(n);i++) 19 #define RD(x) scanf("%d",&x) 20 #define RD2(x,y) scanf("%d%d",&x,&y) 21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 22 #define WN(x) printf("%d\n",x); 23 #define RE freopen("D.in","r",stdin) 24 #define WE freopen("1biao.out","w",stdout) 25 #define mp make_pair 26 #define pb push_back 27 28 const int maxn=111111; 29 const int MOD=1e9+7; 30 31 int n; 32 int a[maxn]; 33 34 struct Edge { 35 int next,v; 36 } e[2*maxn]; 37 int en=0; 38 int head[maxn]; 39 40 void add(int x,int y) { 41 e[en].v=y; 42 e[en].next=head[x]; 43 head[x]=en++; 44 } 45 46 bool u[maxn]; 47 ll f[maxn][2];///f[x][j] j=1表示x所在联通块有黑点，0表示无黑店 的种类数，包括x连接父亲的边和子树所有的边 48 void dfs(int x){ 49 //printf("[in %d]",x); 50 int i; 51 u[x]=1; 52 f[x][0]=1; 53 f[x][1]=0;///先假设当前点是个白点 54 for(i=head[x]; i!=-1; i=e[i].next) { 55 if(!u[e[i].v]) { 56 dfs(e[i].v); 57 f[x][1]=(f[x][1]*f[e[i].v][0] + f[x][0]*f[e[i].v][1])%MOD;///有黑点的情况，先用已经统计的有黑点的情况乘一发儿子没黑点的情况，然后用已经统计的没黑点的情况乘一发儿子有黑点的情况 58 f[x][0]=f[x][0]*f[e[i].v][0]%MOD;///没黑点的情况直接乘儿子没黑点的情况 59 } 60 } 61 u[x]=0; 62 ///下面是对x点的父边的处理 63 if(a[x]==0)f[x][0]=(f[x][0]+f[x][1])%MOD;///x是白点，儿子要是有黑点，砍了x的父边就是没黑点，所以没黑点（f[x][0]）的情况要加上有黑点的情况（f[x][1]） 64 else f[x][1]=f[x][0];///x点是黑点，那不砍父边的情况（f[x][1]）只有让x的儿子都不黑，砍父边的情况（f[x][0]）也是x的儿子都不黑，因为x自己黑嘛，儿子再黑就连到一起了 65 //printf("[out %d,flag=%d,re=%I64d,a[x]=%d]\n",x,flag,re,a[x]); 66 } 67 68 69 ll farm() { 70 if(n==1)return 1; 71 mz(u); 72 dfs(0); 73 return f[0][1]; 74 } 75 76 int main() { 77 int i; 78 int x; 79 RD(n); 80 memset(head,-1,sizeof(head)); 81 en=0; 82 REP(i,n-1) { 83 scanf("%d",&x); 84 add(i+1,x); 85 add(x,i+1); 86 } 87 for(i=0; i<n; i++) 88 scanf("%d",&a[i]); 89 printf("%I64d",farm()); 90 return 0; 91 }