条件を満たす塗り方を直接、木DPで数え上げます。(\(1\) を根としておきます。)

頂点 \(x \in [1, N]\)、条件の集合 \(S \subseteq [1, M]\) に対し、次のものの個数を \(\mathrm{dp}(x, S)\) とおきます。

• 頂点 \(x\) を根とする根付き部分木の辺の塗り方であって、それに属する黒辺によって満たされている条件全体の集合が \(S\) であるもの

すると、答えは \(\mathrm{dp}(1, [1, M])\) です。

木 DP でテーブル \(\mathrm{dp}\) を計算する

これは次のように計算できます。

\[ \mathrm{dp}'(y, T) := \sum _ { T \setminus p(y) \subseteq U \subseteq T } \mathrm{dp}(y, U) \]

(ただし、\(p(y)\) は \(y\) を LCA でない頂点として含む制約パス全体の集合)

\[ \mathrm{dp}(x, S) = \begin{cases} \sum _ { \bigcup _ y T _ y = S } \mathrm{dp}'(y, T) & (\mathrm{if} \ l(x) \subseteq S) \\ 0 & (\mathrm{otherwise}) \end{cases} \]

(ただし、\(l(x)\) は \(x\) を LCA として含む制約パス全体の集合)

1 つ目の遷移は配る DP で \(O(2 ^ M)\) 時間、2 つめの遷移は高速ゼータ変換で \(O(M 2 ^ M)\) 時間でできるので、全体 \(O(NM2 ^ M)\) 時間です。