どうも苦手意識があるので、典型的な解法やテクニックをまとめることにする。 問題を解いたら適宜追加する。未来の自分、よろしく。 動的計画法 dp[盤面] = その盤面からスタートした時に勝つ/負ける として、勝ち負けが自明な状態（決着がついたときとか）…

部分木に対するクエリとかを効率的に行いたいときに便利。 ABC294Gで学んだ。 atcoder.jp やり方 根からdfsしたときに、辺（あるいは頂点）を通った順に記録しておく。 ついでに問題に必要な情報も同じ順番で記録しておく。 こうすると任意の部分木について…