まず、\(k\) を固定したときの答えの求め方を考えます。

\(\{S_1, S_2, \dots ,S_k \}\) をキーとする Trie を作り、全ての頂点が子を \(0\) 個または \(2\) 個持つように適当に頂点を加え、以下のような二分木の問題に言い換えます。

全ての頂点が子を \(0\) 個または \(2\) 個持つ二分木と、頂点の集合 \(T\) が与えられます。\(T\) のうちいくつかの頂点を選んで黒く塗り、他の全ての頂点を白く塗る方法であって、以下の条件を満たすものは何通りあるか？

根から白い頂点のみを辿って葉に辿り着くことが出来ない

この問題は以下のような木 dp で解くことが出来ます。

• \(dp_v=\) \(v\) 以下の部分木内の頂点を、\(v\) から白い頂点のみを辿って葉に辿り着くことが出来ないように塗り分ける場合の数
• 漸化式：
  • \(v\) が葉の場合：
    • \(v\) が \(T\) に含まれぬ場合：\(dp_v = 0\)
    • \(v\) が \(T\) に含まれる場合：\(dp_v = 1\)
  • \(v\) が葉でない場合（\(v\) の \(2\) つの子をそれぞれ \(l,r\) とし、\(v\) 以下の部分木に含まれる \(T\) の頂点の個数を \(C_v\) とします）：
    • \(v\) が \(T\) に含まれぬ場合：\(dp_v = dp_l \times dp_r\)
    • \(v\) が \(T\) に含まれる場合：\(dp_v = dp_l \times dp_r + 2^{C_v-1}\)

次に、上記の問題を全ての \(k\) について高速に解く方法を考えます。\(T\) の頂点が \(1\) 個増える度に \(dp\) および \(C\) を適切に更新することを考えると、これらの値が変化するのは \(v\) から根までのパス上の頂点のみであることが分かります。これらは愚直にボトムアップに更新しても計算量が \(O(|S_k|)\) であり、全体の計算量は \(O(\sum_k |S_k|)\) で十分高速です。（コード）