Educational DP Contest / DP まとめコンテスト P - Independent Set

問題
提出コード

解法

を色としたとき(1:白、0:黒)の、根とする部分木の色の決め方
とします。
全体の根はで固定します。
の子をとします。
すると、を黒で塗るには、の子はすべて白でなければならないこと、を白で塗る場合は、の色は何色でもよいことを考えると、遷移は


となります。
は、の乗算バージョンで、全ての積をとります。
あとは、うまーくの子を拾っていくことができれば、が答えになります。

感想

再帰をして、戻ってくるときに計算をするタイプ、あまり記憶がないので初めてかもしれません。
まずは、いつも通り幅優先か何かを行って計算することを考えましたが、の子が数種類合った場合、そのさらに子にうつったときに、の色をどちらにしたかという情報も必要になったりと、計算が複雑になり、時間内に解くことが難しそうでした。そこで、逆転の発想をして、幅優先探索を行い、葉から根に戻ってくる際に、計算を行っていくことにすれば、の子のさらに子は、とは無縁なので、うまく解くことができそう、という思考に至ります。あとは、と、その子のの関係を立式することができれば、この問題を解くことができます。