全方位木DP [いかたこのたこつぼ]

詳細なアルゴリズムは、他の記事が多く出てくるのでそちら参照。 「木で、ある頂点を中心に考えたときの何らかの値」を「全ての頂点について」求めたいときに使うことがある。 ①を根として木DPを行うことで、①を中心に考えたときの値を求められるような問題があったとする。 このとき、頂点②を中心に考えたいとき、最初からまた木DPを行うのでなく、 ①を計算したときの結果を上手くずらして使うことで、計算量を削減できる。 ① ② ／ ＼ ⇙⇓＼ ②から④,⑤方向への部分木 および ② ③ → ④ ⑤ ① ①から③方向への部分木は /\ /\ ⇓ ①を根としたDPで求まっている（二重矢印） ④⑤ ⑥⑦ ③ ⇙⇘ あとは、親子関係を①→②から②→①に ⑥ ⑦ 付け替えたときの差分を計算すればよい。 （DP[1] から DP[2] に相当する分を除き、 DP[2] にはその除いた分を加える） 1つ頂点を遷移するた