Submission #76081938

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
using pii = pair<ll, ll>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using mint = modint998244353;
// using mint = modint1000000007;
#define endl '\n'
#define OVERLOAD_REP(a, b, c, d, name, ...) name
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define REP0(x) for (ll _rep_counter = 0; _rep_counter < (x); ++_rep_counter)
#define REP1(i, x) for (ll i = 0; (i) < (x); ++(i))
#define REP2(i, l, r) for (ll i = (l); (i) < (r); ++(i))
#define REP3(i, l, r, c) for (ll i = (l); ((c) > 0 ? (i) < (r) : (i) > (r)); i += (c))
#define all(x) (x).begin(), (x).end()
const ll INF = LLONG_MAX / 4;
vi dx = {1, 0, -1, 0, 1, 1, -1, -1};
vi dy = {0, 1, 0, -1, 1, -1, 1, -1};
vc alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vc ALPHABET = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

const int MAX = 2e6;
mint fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    const int MOD = mint::mod();
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i;
        inv[i] = MOD - inv[MOD % i] * (MOD / i);
        finv[i] = finv[i - 1] * inv[i];
    }
}

// 二項係数計算
mint COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[k] * finv[n - k];
}

void io_setup()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(16);
}

int main(void)
{
    io_setup();
    COMinit();
    int n;
    cin >> n;
    vvi g(n);
    rep(i,1,n){
      int p;
      cin >> p;
      p--;
      g[p].push_back(i);
    }
    vi c(n), d(n);
    rep(i,n)cin >> c[i];
    rep(i,n)cin >> d[i];
    
    mint ans = 1;
    vi sum(n), need(n);
    
    bool ok = true;
    
    auto dfs = [&](auto self, int v)->void{
      sum[v] = c[v];
      ll child_need=0;
      for(auto to: g[v]){
        self(self, to);
        
        sum[v]+=sum[to];
        child_need += need[to];
      }
      
      need[v]=child_need + d[v];
      if(need[v]>sum[v])ok=false;
      
      ll nokori = sum[v]-child_need;
      
      ans *= COM(nokori, d[v]);
    };
    
    dfs(dfs, 0);
    
    if(!ok)cout << 0 << endl;
    else cout << ans.val() << endl;
}

Submission Info

Judge Result