ICPC 2017 Latin American Regional G（dp）

[题目连接](https://vjudge.net/problem/Gym-101889G) ------------ 设$dp[x][1][0/1]$为$x$正确输出$0/1$的方案数 $dp[x][0][0/1]$为$x$错误输出$0/1$的方案数 仔细思考状态转移的细节即可 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M=1e5+5,mod=1e9+7; int n,son[M][2],bad[M]; ll dp[M][2][2]; void dfs(int x) { int t1=son[x][0],t2=son[x][1]; if(t1)dfs(t1); if(t2)dfs(t2); dp[x][1][0]=dp[t1][1][1]*dp[t2][1][1]%mod; dp[x][1][1]=(dp[t1][1][0]*dp[t2][1][0]%mod+dp[t1][1][1]*dp[t2][1][0]%mod+dp[t1][1][0]*dp[t2][1][1]%mod +dp[t1][0][1]*dp[t2][1][0]%mod+dp[t1][1][0]*dp[t2][0][1]%mod +dp[t1][1][0]*dp[t2][0][0]%mod+dp[t1][0][1]*dp[t2][0][0]%mod +dp[t1][0][0]*dp[t2][1][0]%mod+dp[t1][0][0]*dp[t2][0][1]%mod)%mod; dp[x][0][1]=(dp[t1][0][0]*dp[t2][1][1]%mod+dp[t1][1][1]*dp[t2][0][0]%mod+dp[t1][0][0]*dp[t2][0][0]%mod)%mod; dp[x][0][0]=(dp[t1][0][1]*dp[t2][0][1]%mod+dp[t1][0][1]*dp[t2][1][1]%mod+dp[t1][1][1]*dp[t2][0][1]%mod)%mod; if(bad[x]==1) { dp[x][0][1]=(dp[x][0][1]+dp[x][1][0])%mod; dp[x][1][0]=0; dp[x][1][1]=(dp[x][1][1]+dp[x][0][0])%mod; dp[x][0][0]=0; } else if(bad[x]==0) { dp[x][0][0]=(dp[x][0][0]+dp[x][1][1])%mod; dp[x][1][1]=0; dp[x][1][0]=(dp[x][1][0]+dp[x][0][1])%mod; dp[x][0][1]=0; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d%d",&son[i][0],&son[i][1],&bad[i]); dp[0][1][0]=1;dp[0][1][1]=1; dfs(1); ll ans=(dp[1][0][0]+dp[1][0][1])%mod; printf("%lld\n",ans); return 0; } ```