繁华模拟赛 Evensgn剪树枝

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const int maxn = ;

const ll mod = ;

struct edge{

    int to;

    int nxt;

};

int n,f[maxn][],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 = ;

    while(b){

        if(b&){

            ans = (ans + a) % mod;

        }

        a = (a + a) % mod;

        b >>= ;

    }

    return ans;

}

ll q_pow(ll a,ll b){

    ll ans = ;

    while(b){

        if(b&){

            ans = q_mul(ans,a);

        }

        a = q_mul(a,a);

        b >>= ;

    }

    return ans;

}

void input(){

    cin>>n;

    int cmd;

    for(int i = ;i < n;i++){

        cin>>cmd;

        add_edge(cmd,i);

    }

    for(int i = ;i < n;i++){

        cin>>col[i];

    }

}

void dfs(int u){

    if(!head[u]){

        if(col[u]) f[u][] = ;

        else f[u][] = ;

        return;

    }

    ll sum = ;

    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][] + f[v][]);

        }

        f[u][] = 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][] + f[v][]);

        }

        f[u][] = sum;

        for(int i = head[u];i;i = e[i].nxt){

            v = e[i].to;

            f[u][] += q_mul(f[v][],q_mul(sum,q_pow(f[v][] + f[v][],mod-)));

        }

        return;

    }

}

int main(){

    freopen("tree.in","r",stdin);

    freopen("tree.out","w",stdout);

    ios::sync_with_stdio(false);

    input();

    dfs();

    cout<<f[][];

    return ;

}

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

using namespace std;

#define ll long long

const int MAXN = 1e5 + ;

const int MOD  = 1e9 + ;

ll f[MAXN][];

int point[MAXN] = {}, nxt[MAXN * ] = {}, v[MAXN * ] = {}, tot = ;

bool color[MAXN] = {};

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][] = ;

    f[now][] = ;

    for (int tmp = point[now]; tmp; tmp = nxt[tmp])

        if (v[tmp] != father)

        {

            dfs(v[tmp], now);

            f[now][] = (f[now][] * f[v[tmp]][]) % MOD;

            f[now][] = (f[now][] + f[now][] * f[v[tmp]][]) % MOD;

            f[now][] = (f[now][] * f[v[tmp]][]) % MOD;

        }

    if (color[now])

        f[now][] = f[now][];

    else

        f[now][] = (f[now][] + f[now][]) % MOD;

}

int main()

{

    freopen("tree.in", "r", stdin);

    freopen("tree.out", "w", stdout);

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

    {

        int x;

        scanf("%d", &x);

        addedge(i, x + ); addedge(x + , i);

    }

    for (int i = ; i <= n; i++)

    {

        int x;

        scanf("%d", &x);

        if (x == ) color[i] = true;

        else color[i] = false;

    }

    dfs(, );

    cout << f[][] << endl;

}