【全方位木DP】明日使える便利な木構造のアルゴリズム - Qiitaこの記事について この記事では、一部で全方位木DP、Rerooting等と呼ばれているアルゴリズムの紹介/解説と、その実装についての簡単な説明を行います。 全方位木DPなどと物騒そうな名前がついていますが、発想自体は全く難しくありません。また、実装もそこまで難しいものではないです。 前提知識として、最低限のグラフ理論の知識(特に木構造について)を要求します。(有向木の根/部分木等…) 謝辞 この記事中に挿入されている図は、殆どを @259_Momone さんに提供して頂きました。素晴らしく美しい図を提供して頂き、この記事を分かりやすいものとして頂いたことに感謝いたします。 全方位木DPとは 各点から深さ優先探索を行って解くことができる問題のうち特定の条件(後述)を満たすものについて、全頂点についての答えを同等の計算量で求めることができるアルゴリズムです。 まず、全方位木DPで解くことができ
