『部分木の答えを有向辺で伝える』全方位木 DP
こんにちは、だいくすとらです (≧▽≦)
先日 X で、以下のような全方位木 DP のポストをしました。ぶっちゃけ、このアルゴリズムのアイデアはこの画像だけでかなり説明できているのですが、より丁寧に解説記事を書いてみました〜💪
解説では式を使って説明していますが、それぞれ図や動画を添えているので「式わかんない!┐(´д｀)┌」という人は図と動画だけ見てもある程度理解できるようにしています！
0. 問題設定
頂点数
の木（連結・閉路なし）が与えられる。 N
各無向辺の長さはすべて (u, v) とする。 1
各頂点について「 r から一番遠い頂点までの距離（辺数）」を求めよ。 r
よくある「各頂点からの最遠距離を全部出してね」というやつです。
素直にやると、各頂点を BFS / DFS の始点にして
ここでは 全方位木 DPを、「頂点ではなく有向辺に DP を載せる」形で説明します。
1. 全体のイメージ：頂点ではなく「辺」に DP を載せる
ふつうの木 DP では「頂点ごとに DP の値を持つ」ことが多いですが、ここでは 無向辺
このとき、有向辺
- 「
u u - ＋ 辺
(u, v)
上の図では、青い部分木の中での最長距離（
つまり
1.1 各頂点の答え ans[v]
頂点
とおけば、
上の図では、頂点
したがって最終的にやることは、すべての有向辺
2. dp[u \to v]
葉
こちらの動画はこの更新式によるDPの値の計算を映像にしたものです。葉から値が木全体に伝搬していくイメージが掴めると思います。
- 画面上: いま計算している辺の様子を映すエリアです。左側に更新式、右側にその式に対応する辺のアニメーションが表示されます。
- 画面下: 計算し終わった
dp[u \to v]
3. 「自分以外の最大値」を素直に求めると重くなる
計算量は下から上の向き(bottom-up)の有向辺の値を計算するときと、上から下の向き(top-down)の有向辺の値を計算するときとで異なります。
bottom-upでは各頂点
一方top-down では以下の式を「
上の図のように、子どもを変えるたびに、毎回ほぼ同じ青い矢印の列を何度も読み込むことになるので、
4. prefix / suffix で「自分以外の最大」を O(1)
4.1 親と子どもを並べる
累積を計算するために木をどこかで根付き木にして、頂点
- 親：
p - 子ども：
c_0, c_1, \dots, c_{k-1} 0
と並べておきます。
4.2 prefix / suffix の定義
頂点
ここで
このとき、子ども
- 左側の最大値：
\mathrm{pref}[i] - 右側の最大値：
\mathrm{suf}[i+1]
がどちらも
4.3 子ども c_i
子ども
- 親方向：
dp[p \to u] u 0 - 左側の子どもたち：
\mathrm{pref}[i] - 右側の子どもたち：
\mathrm{suf}[i+1]
なので更新式は以下のように書けます。
各頂点
そこから各
5. 実装例（Python）
ここまでの内容を、そのまま Python で書いたコードを載せておきます。
- prefix / suffix を使わず、素直に「自分以外の最大」を取り直す
O(N^2) - prefix / suffix を使って
O(N)
の 2 パターンです。どちらも、記事中の簡単なサンプル木をそのままベタ書きしています。
5.1 prefix / suffix なし（O(N^2)
top-down 側で毎回「自分以外の最大値」を取り直している素直な実装です。 アルゴリズムのイメージをつかむ用としては分かりやすいですが、次数が大きい頂点があると計算量が
from collections import deque
# ========= サンプル木 =========
N = 10
EDGES = [
(0, 1),
(0, 2),
(0, 3),
(1, 4),
(1, 5),
(4, 6),
(2, 7),
(7, 8),
(3, 9),
]
tree = [[] for _ in range(N)]
for s, t in EDGES:
tree[s].append(t)
tree[t].append(s)
# ------------------------------------------------------------
# 0. 根付き木にして、親 par と BFS 順 order と children を作る
# ------------------------------------------------------------
par = [-1] * N
order = []
children = [[] for _ in range(N)]
root = 0
q = deque([root])
while q:
u = q.popleft()
order.append(u)
for v in tree[u]:
if v == par[u]:
continue
par[v] = u
children[u].append(v)
q.append(v)
# dp[u][v] = 有向辺 u -> v に載せる値
dp = [{v: 0 for v in adj} for adj in tree]
# ------------------------------------------------------------
# 1. bottom-up
# ------------------------------------------------------------
for u in reversed(order):
v = par[u]
if v == -1:
continue
dp[u][v] = 1 + max(
(dp[x][u] for x in tree[u] if x != v),
default=0,
)
# ------------------------------------------------------------
# 2. top-down（毎回「自分以外の最大」を取り直す）
# ------------------------------------------------------------
for u in order:
for v in children[u]:
dp[u][v] = 1 + max(
(dp[x][u] for x in tree[u] if x != v),
default=0,
)
# ------------------------------------------------------------
# 3. 各頂点 v に「入る」有向辺の最大値が
# 「v から最も遠い頂点までの距離」になる。
# ------------------------------------------------------------
ans = []
for v in range(N):
ans.append(max(dp[x][v] for x in tree[v]))
print(*ans)
5.2 prefix / suffix を使った高速版（O(N)
本文で解説した「有向辺 DP + prefix / suffix」による高速版です。
from collections import deque
from itertools import accumulate
# ========= サンプル木 =========
N = 10
EDGES = [
(0, 1),
(0, 2),
(0, 3),
(1, 4),
(1, 5),
(4, 6),
(2, 7),
(7, 8),
(3, 9),
]
tree = [[] for _ in range(N)]
for s, t in EDGES:
tree[s].append(t)
tree[t].append(s)
# ------------------------------------------------------------
# 0. 根付き木にして、親 par と BFS 順 order と children を作る
# ------------------------------------------------------------
par = [-1] * N
order = []
children = [[] for _ in range(N)]
root = 0
q = deque([root])
while q:
u = q.popleft()
order.append(u)
for v in tree[u]:
if v == par[u]:
continue
par[v] = u
children[u].append(v)
q.append(v)
# dp[u][v] = 有向辺 u -> v に載せる値
dp = [{v: 0 for v in adj} for adj in tree]
# ------------------------------------------------------------
# 1. bottom-up: dp[u][v] = 1 + max( dp[x][u] (x != v) )
# ------------------------------------------------------------
for u in reversed(order):
v = par[u]
if v == -1:
continue
dp[u][v] = 1 + max(
(dp[x][u] for x in tree[u] if x != v),
default=0,
)
# ------------------------------------------------------------
# 2. prefix / suffix
# ------------------------------------------------------------
pref = [[] for _ in range(N)]
suf = [[] for _ in range(N)]
for u in range(N):
vals = [dp[v][u] for v in children[u]]
# pref[u][i] = children[u][:i] から来る最大値
pref[u] = [0] + list(accumulate(vals, max))
# suf[u][i+1] = children[u][i+1:] から来る最大値
suf[u] = list(accumulate(reversed(vals), max))[::-1] + [0]
# ------------------------------------------------------------
# 3. top-down: dp[u][v] = 1 + max( par_in, pref[u][i], suf[u][i+1] )
# ------------------------------------------------------------
for u in order:
p = par[u]
par_in = dp[p][u] if p != -1 else 0
for i, v in enumerate(children[u]):
dp[u][v] = 1 + max(par_in, pref[u][i], suf[u][i + 1])
# ------------------------------------------------------------
# 4. 各頂点 v に「入る」有向辺の最大値が
# 「v から最も遠い頂点までの距離」になる。
# ------------------------------------------------------------
ans = [max(dp[x][v] for x in tree[v]) for v in range(N)]
print(*ans)
6. まとめ
この全方位木 DP は、各有向辺に「自分側の部分木情報＋1」を載せて葉から木全体へと伝搬させることで、どの頂点を根にしても成り立つ情報を計算するテクニックです。さらに、各頂点で必要になる「自分以外の最大値」を prefix / suffix でまとめて求めることで、素朴な実装では
もし分からないところやここ間違ってるよ！とかがあったら気軽にコメントで教えてください！
宣伝
自分はうさねこらーじさんプロデュースの VTuber グループ「はぴねすと∞」からデビュー予定です！
2026/2/11 に初配信を予定しているので、よかったら遊びに来てください〜
📺 初配信はこちら
また、はぴねすと∞の各メンバーの X アカウントも載せておきます。
みんな魅力的な人ばかりなので、気になったメンバーがいたらぜひフォローしてもらえると嬉しいです！
Discussion