#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 2e5 + 1;
const int MOD = 1000002022;
vector<ll> grafo[MAXN];
ll val[MAXN];
ll n, m, tot = 0;
pair<ll, ll> dfs(ll nod) // fr: posibilidades activo, se: posibilidades apagado
{
if (nod >= n)
return {val[nod], !val[nod]};
pair<ll, ll> cant = {0, 0};
ll tot = 1;
vector<pair<ll, ll>> s;
vector<ll> pref, suf;
for (auto k : grafo[nod]) {
pair<ll, ll> a = dfs(k);
s.pb(a);
tot = (tot * (a.fr + a.se) % MOD) % MOD;
}
int c = sz(s); // Número de hijos
pref.resize(c);
pref[0] = 1;
suf.resize(c);
suf[c - 1] = 1;
for (int i = 1; i < c; i++)
pref[i] = (pref[i - 1] * (s[i - 1].fr + s[i - 1].se) % MOD) % MOD;
for (int i = c - 2; i >= 0; i--)
suf[i] = (suf[i + 1] * (s[i + 1].fr + s[i + 1].se) % MOD) % MOD;
for (int i = 0; i < c; i++)
cant.fr = (cant.fr + (s[i].fr * (pref[i] * suf[i]) % MOD) % MOD) % MOD;
cant.se = ((tot * (ll)c % MOD) - cant.fr + MOD) % MOD; // Corrección: todo en una línea
return cant;
}
void calc() {
pair<ll, ll> a = dfs(0);
tot = a.fr;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
ll i;
for (i = 1; i < sz(P); i++)
grafo[P[i]].pb(i);
for (i = 0; i < sz(A); i++)
val[i + N] = A[i];
n = N;
m = M;
}
int count_ways(int L, int R) {
ll i;
for (i = L; i <= R; i++)
val[i] = !val[i];
calc();
return tot;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |