首页 > 代码库 > CF461B Appleman and Tree （树DP）
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 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 long14 #define usll unsigned ll15 #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_pair26 #define pb push_back27 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 }
CF461B Appleman and Tree （树DP）