首页 > 代码库 > 繁华模拟赛 Evensgn剪树枝
繁华模拟赛 Evensgn剪树枝
#include<iostream> #include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<cmath>#define ll long longusing namespace std;const int maxn = 100005;const ll mod = 1000000007;struct edge{ int to; int nxt;};int n,f[maxn][2],col[maxn];int cnt,head[maxn];edge e[maxn];void add_edge(int u,int v){ cnt++; e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;}ll q_mul(ll a,ll b){ ll ans = 0; while(b){ if(b&1){ ans = (ans + a) % mod; } a = (a + a) % mod; b >>= 1; } return ans;}ll q_pow(ll a,ll b){ ll ans = 1; while(b){ if(b&1){ ans = q_mul(ans,a); } a = q_mul(a,a); b >>= 1; } return ans;}void input(){ cin>>n; int cmd; for(int i = 1;i < n;i++){ cin>>cmd; add_edge(cmd,i); } for(int i = 0;i < n;i++){ cin>>col[i]; }}void dfs(int u){ if(!head[u]){ if(col[u]) f[u][1] = 1; else f[u][0] = 1; return; } ll sum = 1; int v; if(col[u]){ for(int i = head[u];i;i = e[i].nxt){ v = e[i].to; dfs(v); sum = q_mul(sum,f[v][0] + f[v][1]); } f[u][1] = sum; return; }else{ for(int i = head[u];i;i = e[i].nxt){ v = e[i].to; dfs(v); sum = q_mul(sum,f[v][0] + f[v][1]); } f[u][0] = sum; for(int i = head[u];i;i = e[i].nxt){ v = e[i].to; f[u][1] += q_mul(f[v][1],q_mul(sum,q_pow(f[v][0] + f[v][1],mod-2))); } return; }}int main(){ freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); ios::sync_with_stdio(false); input(); dfs(0); cout<<f[0][1]; return 0;}#include <cstdio>#include <cmath>#include <cstring>#include <cstdlib>#include <iostream>using namespace std;#define ll long longconst int MAXN = 1e5 + 10;const int MOD = 1e9 + 7;ll f[MAXN][2];int point[MAXN] = {0}, nxt[MAXN * 2] = {0}, v[MAXN * 2] = {0}, tot = 0;bool color[MAXN] = {0};int n;inline void addedge(int x, int y){ tot++; nxt[tot] = point[x]; point[x] = tot; v[tot] = y;}void dfs(int now, int father){ f[now][0] = 1; f[now][1] = 0; for (int tmp = point[now]; tmp; tmp = nxt[tmp]) if (v[tmp] != father) { dfs(v[tmp], now); f[now][1] = (f[now][1] * f[v[tmp]][0]) % MOD; f[now][1] = (f[now][1] + f[now][0] * f[v[tmp]][1]) % MOD; f[now][0] = (f[now][0] * f[v[tmp]][0]) % MOD; } if (color[now]) f[now][1] = f[now][0]; else f[now][0] = (f[now][0] + f[now][1]) % MOD;}int main(){ freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); scanf("%d", &n); for (int i = 2; i <= n; i++) { int x; scanf("%d", &x); addedge(i, x + 1); addedge(x + 1, i); } for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); if (x == 1) color[i] = true; else color[i] = false; } dfs(1, 0); cout << f[1][1] << endl;}
繁华模拟赛 Evensgn剪树枝
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。