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 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]是这个联通块有黑点的种类数。
太难了！怪不得大家都掉分飞起，虽然题解的代码看起来很短，我根本想不出来啊看了半天还是不懂啊！
具体还是看代码吧，写了点注释，这个统计方法太碉了，我也弄得不是很清楚，算了日后再说。
代码：
//#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 ;
}