#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) typedef long long ll; const int N = 200005, M = 1000002022; int n, m; vector<int> g[N]; int a[N]; int dp[N]; void dfs(int x) { a[x] = 1; if (g[x].empty()) return; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; dfs(h); a[x] = (a[x] * 1LL * a[h]) % M; } a[x] = (a[x] * 1LL * sz(g[x])) % M; vector<int> p; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (p.empty()) p.push_back(a[h]); else p.push_back((p.back() * 1LL * a[h]) % M); } vector<int> s; for (int i = sz(g[x]) - 1; i >= 0; --i) { int h = g[x][i]; if (s.empty()) s.push_back(a[h]); else s.push_back((s.back() * 1LL * a[h]) % M); } reverse(all(s)); dp[x] = 0; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; int yans = dp[h]; if (i) yans = (yans * 1LL * p[i - 1]) % M; if (i + 1 < sz(g[x])) yans = (yans * 1LL * s[i + 1]) % M; dp[x] = (dp[x] + yans) % M; } } void init(int NN, int MM, std::vector<int> P, std::vector<int> A) { n = NN; m = MM; for (int i = 1; i < n + m; ++i) g[P[i]].push_back(i); for (int i = 0; i < m; ++i) dp[n + i] = A[i]; } int count_ways(int L, int R) { for (int i = L; i <= R; ++i) dp[i] ^= 1; dfs(0); return dp[0]; } /* 3 4 3 -1 0 1 2 1 1 0 1 0 1 0 3 4 4 5 3 6 */

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
circuit.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
circuit.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~