ABC 152 F Tree and Constraints 解説
パスを求める
dfs をして v[i] -> u[i] のパスを求めておく．このパス上に含まれる辺の集合を p[i] と置く．
問題の言い換え
以上により，この問題は次のように変換された．
N-1 個の白い辺があり，いくつかを黒く塗る．このとき，各 i (1 <= i <= M) について集合 p[i] に含まれる辺のうちいずれか一つは黒く塗られていなければならない．
bitDP
状態の持ち方は dp[N-1][2M] といった感じ．
各辺を順番に見ていく．今 dp[i][s] だとして，遷移は次の 2 パターンがある．
- その辺を黒く塗らない dp[i+1][s]
- その辺を黒く塗る dp[i+1][s2]
ただし，もしその辺が M 個の集合 p のいずれかに含まれていたら，s の対応する bit を立たせる．(立たせたものが s2)
最後に，n == N-1 のとき，s のすべての bit がちゃんと立っていれば return 1，立ってなかったら return 0．
時間計算量
- パスを求める部分の計算量が O(NM)
- bitDP をする部分の計算量が O(N 2M)
よって，全体では O(N(M+2M))
