深さ優先探索において,引数に母親を指定する
久々の更新ですが,メモを書いておきます. 深さ優先探索において,母親を指定しておくと一回行ったかどうかを判定しなくてもいい.
void dfs (ll i, ll pa = -1) { dp[i][0] = 1; dp[i][1] = 1; for (auto j : box[i]) { if (j != pa) { dfs(j, i); dp[i][0] = ((dp[i][0] % mod) * ((dp[j][0] + dp[j][1]) % mod)) % mod; dp[i][1] = ((dp[i][1] % mod) * (dp[j][0] % mod)) % mod; } } }