CF 461 B Appleman and Tree 题解（树形 dp+排列组合）

原题传送门

思路

求方案数，肯定是排列组合，dp 一类的，猜测此题为树形 dp。先写出 $d{p}_i$，发现无法决定是否截断，得要看连通块里有没有黑色的节点，变成两维 $d{p}_{i,0/1}$ 就可以判断了。（本人很懒，所以直接祭出自己的笔记本，字丑见谅）

代码

注意：

1. 要取模，写乘法逆元。
2. 节点编号从零开始，建议集体加一。集体加一的情况下，输入的 $p_0$ 加上 1 表示 2 连到的节点。
3. 边界条件是 go[ps].size()<=1&&fa!=0，因为如果是根节点，只有一条边连出去表示只有一个儿子而不是没有儿子。

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int n,x,c[100005];
long long dp[100005][2];
vector<int> go[100005];
long long mi(long long x,int y){if(y==1) return x;long long t=mi(x,y/2);return t*t%mod*(y%2?x:1)%mod;
}
void dfs(int ps,int fa){if(go[ps].size()<=1&&fa!=0){dp[ps][c[ps]]=1;return;}for(auto j:go[ps]) if(j!=fa) dfs(j,ps);int i=ps;if(c[ps]){dp[i][1]=1;for(auto j:go[ps]) if(j!=fa)dp[i][1]=dp[i][1]*((dp[j][0]+dp[j][1])%mod)%mod;}else{dp[i][0]=1;for(auto j:go[ps]) if(j!=fa)dp[i][0]=dp[i][0]*((dp[j][0]+dp[j][1])%mod)%mod;for(auto j:go[ps]) if(j!=fa)dp[i][1]=(dp[i][1]+dp[i][0]*dp[j][1]%mod*mi(dp[j][0]+dp[j][1],mod-2)%mod)%mod;}
}
int main(){cin>>n;for(int i=2;i<=n;i++){cin>>x;x++;go[i].push_back(x);go[x].push_back(i);}for(int i=1;i<=n;i++) cin>>c[i];dfs(1,0);cout<<dp[1][1]<<endl;return 0;
}