首页 > 代码库 > 繁华模拟赛 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剪树枝