ABC222 E - Red and Blue Tree (500)
まずAの通りに移動して、それぞれの辺が何回使われるかを求める
合計の移動回数とkの偶奇が異なる場合、達成不可能なので答えは0
R,Bの少ない方の回数が0未満になる場合も答えは0
$ dp[i][j] でi番目までの辺を色分けして$ R-B=jとなる場合の数とする
$ dp[i][j] = dp[i-1][j] + dp[i-1][j-cnt_i]
一度も使われていない辺は飛ばす
一度も使われていない辺は色を自由に決めることができるので、最後に$ 2^{使われていない辺の数}を答えに掛ける
辺の使われた回数を求めるのが$ \mathcal{O}(NM)、DPが$ \mathcal{O}(N^2M)