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;
}

原文地址：https://blog.csdn.net/2401_84512298/article/details/142468217

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！