深さ優先探索のテンプレート
引数の頂点変数について、大雑把な方針としては
- 頂点インデックスが不要なとき→頂点の値 vx
- 陽にグラフを持つときなど→頂点インデックス vi
状態はオーバーヘッドが大きいことが多いのでグローバルで持ち、保存処理と復元処理を追加する
陽にグラフ構造を持つ深さ優先探索のときは頂点を記録するvis配列を用意して無限ループを防ぐ
auto dfs=[&](auto self,現在の頂点viまたはvx)->void { if(再帰の終了条件) return; （必要ならば）vis[vi]=true; 遷移する前の計算 for(次の頂点nviまたはnvx) { if(遷移しない条件) continue; （必要ならば）状態の保存処理 nviまたはnvxに遷移するときの計算 self(self,次の頂点nviまたはnvx); （必要ならば）状態の復元処理 } 全ての子頂点 (nviまたはnvx) から戻ってきたときにする計算 };
メモ化する深さ優先探索のテンプレート
ABC340C - Divide and Divide
ソースコード
- いわゆるメモ化と言われているテク、mapを参照することで計算量を削減する
- sum_cvx[vx] (sum child vx) の計算は全ての子頂点から帰ってきた後なので for の後に書く
- dfs実行前にsum_cvx[1]の値を初期化しないとout of rangeになるので注意する
mll sum_cvx; auto dfs lam(auto self,ll vx)vo { if(vx==1) return; vl nvxs; if(!lfind(sum_cvx,ldivc(vx,2))) pushb(nvxs,ldivc(vx,2)); if(!lfind(sum_cvx,ldivf(vx,2))) pushb(nvxs,ldivf(vx,2)); forx(nvx,nvxs) self(self,nvx); sum_cvx[vx]=vx+sum_cvx[ldivc(vx,2)]+sum_cvx[ldivf(vx,2)]; }; sum_cvx[1]=0; dfs(dfs,N);
mll sum_cvx; auto dfs lam(auto self,ll vx)ll { if(lfind(sum_cvx,vx)) return sum_cvx[vx]; sum_cvx[vx]=vx+self(self,ldivc(vx,2))+self(self,ldivf(vx,2)); return sum_cvx[vx]; }; sum_cvx[1]=0; dfs(dfs,N);
- OEIS を使えば1行で済む
out(N*llogf(2,4*N)-lpow(2,(llogf(2,2*N))));
陽にグラフを持つ深さ優先探索のテンプレート
ABC138D - Ki
ソースコード
- 頂点に遷移したかどうか記録するvis配列を用意して無限ループを防ぐ
- sum_pvx[nvi] (sum parent vx) は親頂点の合計になるので、遷移直前に計算する
- dfs実行前に根の初期化を忘れないようにする
vb vis(N); vl sum_pvx(N); auto dfs lam(auto self,ll vi)vo { vis[vi]=true; forx(nvi,nvx,g[vi]) { if(!!vis[nvi]) continue; sum_pvx[nvi]=sum_px[nvi]+sum_pvx[vi]; self(self,nvi); } }; sum_pvx[0]=sum_px[0]; dfs(dfs,0);
