メモ帳

「 頂点の木において、 を根としたときの○○をそれぞれ求めよ」というタイプの問題では、全方位木DP(ReRooting)が有効に働く場合が多いです。 根を1つ固定したときにこの問題が高速に解けるならば、全方位木DPを用いることで同じ計算量で全ての根についての問題を解くことが出来ます。 この記事では主に実装方法について述…