自然な順向きのDPや公式解法の「解法１」において、DP の状態数は約 \(2\times 10^8\) 個であり、32 bit 整数でこれを管理しようとすると 750 MiB ほど必要になり MLE します。

対して、愚直な DFS では、問題文に「採点用入力データでは配る道順が 2000000 通りをこえることはない．」とあっても、間に合う保証はありません。

しかし、「ここから最終状態に到達できない」ということが高速に分かれば、DFS において枝刈りが効いて 2000000 × (家の数) の線形の計算量で求まります。

bool値DP

逆向きに DP を行い、「最終状態に到達可能か？」ということを bool 値で求めます。

vector や bitset では bool 値は 1 bit で管理できるので、このDPはすべて持っても 24 MiB ほどになり、メモリ制限に間に合います。

そのメモした DP を用いて、DFSを行うと間に合います。