余事象を考えて包除原理を用いる問題に出会う度、理解に時間がかかるのでメモ。「すべて～ない」などの条件をもった場合の数を直接求めるのは難しく、否定の条件を考えて余事象で求めることがある。 例えば、求める条件が任意の に対して であるというときに…

全方位木 DP の抽象化を書いてみた。 コードと使用例のみ。(使用例はネタバレあり)気が向いたら解説を書くかもしれない、未来の自分に期待。 少しだけ書くと、rerooting_function では、子ノードの subtree_dp の累積を両側から取って、それぞれの子ノードに…

読みやすさを考慮していないので、詳しく知りたい人は最後に載せたリンク先を参照したりしてほしい。 図や表を気休め程度に載せているが、それを手で書いたりしていると理解が深まるかもしれない。 自分はそうしてやっと理解している気になった。まず木を区…