rerooting

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /rerooting#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /rerooting#noredirect を利用してください。
name
rerooting
short description
rerooting とは、根付きでない木 $T$ と根付き木の畳み込み $f$ (いわゆる木 DP) が与えられたとき、それぞれの頂点 $r \in T$ に対しそれを根とした根付き木 $T_r$ に対する畳み込み結果 $f(T_r)$ を $O(N)$ ですべて求めるアルゴリズムである。全方位木 DP とも呼ばれる。