2022-05-06 EDPC の P を解いた
EDPC : Educational DP Contest の P を解いた。
- P - Independent Set
https://atcoder.jp/contests/dp/tasks/dp_p
- 提出: https://atcoder.jp/contests/dp/submissions/31469717
- 木 DP
- 葉から順 (DFS の帰りがけ順) に頂点ごとの場合の数を確定していく
- 葉は白のとき 1 黒のとき 1
- 葉以外は白のとき子の白と黒の和の積 黒のとき白の積
- 根における場合の数が答えになる
今日のコミット。