解法
を色
としたとき(1:白、0:黒)の、根とする部分木の色の決め方
とします。
全体の根はで固定します。
の子を
とします。
すると、を黒で塗るには、
の子
はすべて白でなければならないこと、
を白で塗る場合は、
の色は何色でもよいことを考えると、遷移は
となります。
は、
の乗算バージョンで、全ての積をとります。
あとは、うまーくの子を拾っていくことができれば、
が答えになります。
感想
再帰をして、戻ってくるときに計算をするタイプ、あまり記憶がないので初めてかもしれません。
まずは、いつも通り幅優先か何かを行って計算することを考えましたが、の子が数種類合った場合、そのさらに子にうつったときに、
の色をどちらにしたかという情報も必要になったりと、計算が複雑になり、時間内に解くことが難しそうでした。そこで、逆転の発想をして、幅優先探索を行い、葉から根に戻ってくる際に、計算を行っていくことにすれば、
の子のさらに子は、
とは無縁なので、うまく解くことができそう、という思考に至ります。あとは、
と、その子の
の関係を立式することができれば、この問題を解くことができます。
