#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define SF scanf #define PF printf #define MAXN 1010 #define INF 0x3FFFFFFF #define MOD 1000000007 using namespace std; typedef long long ll; vector<int> son[MAXN],ison[MAXN],spe; ll dp[MAXN][2],calc[MAXN][2],minans=INF,tot; int sta[MAXN]; void dfs(int x){ dp[x][0]=0,dp[x][1]=1; calc[x][0]=1,calc[x][1]=1; for(int i=0;i<int(son[x].size());i++){ int u=son[x][i]; dfs(u); dp[x][0]+=dp[u][1]; calc[x][0]=calc[x][0]*calc[u][1]%MOD; if(dp[u][0]<dp[u][1]){ dp[x][1]+=dp[u][0]; calc[x][1]=calc[x][1]*calc[u][0]%MOD; } else if(dp[u][0]>dp[u][1]){ dp[x][1]+=dp[u][1]; calc[x][1]=calc[x][1]*calc[u][1]%MOD; } else{ dp[x][1]+=dp[u][0]; calc[x][1]=calc[x][1]*(calc[u][0]+calc[u][1])%MOD; } } for(int i=0;i<int(ison[x].size());i++) if(sta[ison[x][i]]==0){ dp[x][0]=INF; calc[x][0]=0; break; } if(sta[x]==0){ dp[x][1]=INF; calc[x][1]=0; } if(sta[x]==1){ dp[x][0]=INF; calc[x][0]=0; } // PF("<%d %lld %lld %lld>\n",x,dp[x][0],dp[x][1]); } class VampireTreeDiv2{ public: int countMinSamples(vector<int> pp1,vector<int> pp2){ memset(sta,-1,sizeof sta); int n=pp1.size(); // SF("%d",&n); // pp1.resize(n); // pp2.resize(n); // for(int i=0;i<n;i++) // SF("%d",&pp1[i]); // for(int i=0;i<n;i++) // SF("%d",&pp2[i]); for(int i=0;i<n;i++){ if(pp1[i]<pp2[i]) swap(pp1[i],pp2[i]); if(pp2[i]==-1) son[pp1[i]].push_back(i+1); else{ son[pp1[i]].push_back(i+1); ison[pp2[i]].push_back(i+1); spe.push_back(i+1); } } int cnt=spe.size(); for(int mask=0;mask<(1<<cnt);mask++){ for(int j=0;j<cnt;j++){ if((mask>>j)&1) sta[spe[j]]=0; else sta[spe[j]]=1; } dfs(0); if(dp[0][0]<minans){ minans=dp[0][0]; tot=calc[0][0]; } else if(dp[0][0]==minans){ tot=(tot+calc[0][0])%MOD; } if(dp[0][1]<minans){ minans=dp[0][1]; tot=calc[0][1]; } else if(dp[0][1]==minans){ tot=(tot+calc[0][1])%MOD; } // PF("[%d %lld]\n",mask,minans); } return tot; // PF("%lld",tot); } };
