Evensgn 剪树枝
题目
繁华中学有一棵苹果树。苹果树有 n 个节点(也就是苹果),n − 1 条边(也就
是树枝)。调皮的 Evensgn 爬到苹果树上。他发现这棵苹果树上的苹果有两种:一
种是黑苹果,一种是红苹果。Evensgn 想要剪掉 k 条树枝,将整棵树分成 k + 1 个
部分。他想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝
的方案?
INPUT
第一行一个数字 n,表示苹果树的节点(苹果)个数。
第二行一共 n − 1 个数字 p0, p1, p2, p3, ..., pn−2,pi 表示第 i + 1 个节点和 pi 节
点之间有一条边。注意,点的编号是 0 到 n − 1。
第三行一共 n 个数字 x0, x1, x2, x3, ..., xn−1。如果 xi 是 1,表示 i 号节点是黑
苹果;如果 xi 是 0,表示 i 号节点是红苹果。
OUTPUT
输出一个数字,表示总方案数。答案对$10^{9}+7$取模
SAMPLE
INPUT
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
OUTPUT
27
解题报告
考试就没咋打这题,于是就骗了十分
正解:
树规
我们设$has[i]$表示节点$i$及其子树带一个黑苹果对父节点产生的方案数贡献
$no[i]$表示节点$i$及其子树不带黑苹果对父节点产生的方案数贡献
我们从叶节点开始讨论
当该叶子为红苹果时,显然无法对父节点产生带黑苹果的方案数贡献,而且它是叶子节点,所以可以对父节点产生$1$的不带黑苹果的方案数贡献,故:
$$has[i]=1,no[i]=0$$
当该节点为黑苹果时,显然可以对父节点产生带黑苹果的方案数贡献,而且它是叶子节点,所以可以对父节点产生$1$的带一个黑苹果的方案数贡献。我们再考虑,当我们砍断它与父节点之间的边时,它也可以对父节点产生$1$的不带黑苹果的方案数贡献,故:
$$has[i]=1,no[i]=1$$
当该节点不为叶子节点时:
假如该节点为黑苹果,那么显然,它的子树无法对他产生带一个黑苹果的方案数贡献(我们先假设它的子树可以,那么,以该节点为根节点的子树就一定有两个或以上的黑苹果,显然是不合法的方案,故舍去)
所以,它的子树对它只能产生不带黑苹果的方案数贡献。
由乘法原理:
$$prod^{}_{jin son[i]}no[j]$$
并且,由与黑苹果叶子节点同样的推理方式,我们可以得到:
$$no[i]=has[i]$$
原因仍然是砍断它与父节点之间的边所能造成的贡献
假如该节点为红苹果,我们先考虑$has[i]$,因为它是一个红苹果,所以它自己不能产生对父节点带一个黑苹果的贡献,所以,我们要对子树的$has[j]$进行处理,我们考虑,当该节点的某一棵子树产生了一个黑苹果的贡献时,其它子树就不能再贡献黑苹果了,所以,我们枚举每一棵子树的$has$值,与其它子树的$no$值相乘(同样是乘法原理)(注意这里,实际上有赌数据的成分,假如数据给个菊花树,瞬间爆炸,菊花树:除了根节点,其他点深度均为1,即根节点为所有其他点的父节点的树的简称,然而还是跑的贼快2333),再取和即为其值,即:
$$has[i]=sum ^{}_{jin son[i]}(has[i] imes prod^{}_{kin son[i] k eq j}no[k])$$
再考虑$no$值就很简单了,首先,假如它的子树都不产生黑苹果贡献,那么它自然不可以对父节点产生贡献,所以首先取个累乘,接着,假如它的子树产生了黑苹果贡献,只要我们砍掉它与父节点之间的边,它仍然可以产生该贡献,所以:
$$no[i]=prod^{}_{jin son[i]}no[j]+has[i]$$
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 inline int read(){ 6 int sum(0); 7 char ch(getchar()); 8 for(;ch<'0'||ch>'9';ch=getchar()); 9 for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 10 return sum; 11 } 12 const int mod=1000000007; 13 struct edge{ 14 int e,n; 15 }a[200005]; 16 int pre[100005],tot; 17 inline void insert(int s,int e){ 18 a[++tot].e=e; 19 a[tot].n=pre[s]; 20 pre[s]=tot; 21 } 22 typedef long long L; 23 int fa[100005]; 24 int n; 25 int w[100005]; 26 L has[100005],no[100005]; 27 inline void dfs(int u){ 28 bool flag(false); 29 for(int i=pre[u];i!=-1;i=a[i].n){ 30 int e(a[i].e); 31 if(e!=fa[u]){ 32 fa[e]=u; 33 flag=true; 34 dfs(e); 35 } 36 } 37 if(!flag){ 38 if(w[u]==0){ 39 has[u]=0; 40 no[u]=1; 41 return; 42 } 43 has[u]=no[u]=1; 44 return; 45 } 46 if(w[u]==1){ 47 has[u]=no[u]=1; 48 for(int i=pre[u];i!=-1;i=a[i].n){ 49 int e(a[i].e); 50 if(e!=fa[u]) 51 has[u]=no[u]=(no[u]*no[e])%mod; 52 } 53 return; 54 } 55 has[u]=0; 56 for(int i=pre[u];i!=-1;i=a[i].n){ 57 int e1(a[i].e); 58 if(e1==fa[u]) 59 continue; 60 L tmp(has[e1]); 61 for(int j=pre[u];j!=-1;j=a[j].n){ 62 int e2(a[j].e); 63 if(e1==e2||e2==fa[u]) 64 continue; 65 tmp=(tmp*no[e2])%mod; 66 } 67 has[u]=(has[u]+tmp)%mod; 68 } 69 no[u]=1; 70 for(int i=pre[u];i!=-1;i=a[i].n){ 71 int e(a[i].e); 72 if(e==fa[u]) 73 continue; 74 no[u]=(no[u]*no[e])%mod; 75 } 76 no[u]=(no[u]+has[u])%mod; 77 } 78 int main(){ 79 memset(fa,-1,sizeof(fa)); 80 memset(pre,-1,sizeof(pre)); 81 n=read(); 82 for(int i=1;i<n;i++){ 83 int x(read()); 84 insert(x,i),insert(i,x); 85 } 86 for(int i=0;i<n;i++) 87 w[i]=read(); 88 dfs(0); 89 printf("%lld",has[0]); 90 }