Javaで考える「木構造の距離計算」をもっと深く理解する（後半）
前半では、 木構造における距離の定義 Javaで木を隣接リストとして表現する方法 DFSで「深さ」と「親」を求める基本パターン 距離を「深さ」と「共通祖先」でイメージする感覚 を整理しました。
後半では、そこから一歩進んで、 最小共通祖先（LCA）を使った距離の公式、 具体的な計算例、 素朴なLCAアルゴリズム、 距離計算と木DP・グラフ探索とのつながり、 そしてセキュリティ・パフォーマンスの観点まで含めて、 「距離計算を武器として使えるレベル」まで深掘りしていきます。
距離の公式：LCAを使って一気に計算する
木構造の距離計算で中心になるのが、次の公式です。
距離
ここで は「根からノード x までの距離（深さ）」 は「u と v の最小共通祖先（Lowest Common Ancestor）」 を表します。
この公式の意味を、直感的にほどいてみます。
まず、u と v のそれぞれについて、根までの距離が 、 です。
一方、LCA を L とすると、 u から L までの距離は v から L までの距離は になります。
したがって、u から v への距離は
となります。
このように、距離は「深さ」と「LCAの深さ」だけで一気に計算できます。 重要なのは、「パスを実際に辿らなくても、事前に計算した情報だけで距離が出せる」という点です。
具体例で距離の公式を確認する
前半で使った木をもう一度思い出します。
根 1 その子が 2 と 3 2 の子が 4 と 5
DFSで深さを計算すると、
depth[1] = 0 depth[2] = 1 depth[3] = 1 depth[4] = 2 depth[5] = 2
になります。
ここで、ノード 4 と 5 の距離を公式で計算してみます。
4 の祖先は 4 → 2 → 1 5 の祖先は 5 → 2 → 1 最小共通祖先 LCA(4, 5) は 2 です。
したがって、
距離は
となり、 実際にパス 4 → 2 → 5 を辿ったときの辺の本数 2 と一致します。
同様に、4 と 3 の距離を計算してみます。
4 の祖先は 4 → 2 → 1 3 の祖先は 3 → 1 最小共通祖先 LCA(4, 3) は 1 です。
距離は
となり、 パス 4 → 2 → 1 → 3 の辺の本数 3 と一致します。
このように、距離の公式は「深さ」と「LCAの深さ」を使って、 パスを辿らずに距離を一発で計算できる強力な道具です。
素朴なLCAアルゴリズムをJavaで書いてみる
距離の公式を使うためには、LCA（最小共通祖先）を求める必要があります。 まずは、初心者向けに分かりやすい「素朴なLCAアルゴリズム」を見てみます。
前半で用意した depth[] と parent[] を使います。
考え方は次の通りです。
- u と v の深さが違う場合、深い方を親に上げて、深さを揃える
- 深さが揃ったら、u と v を同時に親に上げていき、同じノードになったところが LCA
これをそのままコードにすると、次のようになります。
public class LCAExample {
static List<Integer>[] tree;
static int[] depth;
static int[] parent;
@SuppressWarnings("unchecked")
public static void main(String[] args) {
int n = 5;
tree = new ArrayList[n + 1];
depth = new int[n + 1];
parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
tree[i] = new ArrayList<>();
}
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
dfs(1, -1, 0);
int u = 4;
int v = 5;
int lca = lca(u, v);
int dist = depth[u] + depth[v] - 2 * depth[lca];
System.out.println("LCA(" + u + ", " + v + ") = " + lca); // 2
System.out.println("dist(" + u + ", " + v + ") = " + dist); // 2
}
static void addEdge(int a, int b) {
tree[a].add(b);
tree[b].add(a);
}
static void dfs(int node, int p, int d) {
parent[node] = p;
depth[node] = d;
for (int next : tree[node]) {
if (next == p) continue;
dfs(next, node, d + 1);
}
}
static int lca(int u, int v) {
// 深さを揃える
while (depth[u] > depth[v]) {
u = parent[u];
}
while (depth[v] > depth[u]) {
v = parent[v];
}
// 同時に親に上がる
while (u != v) {
u = parent[u];
v = parent[v];
}
return u;
}
}
このコードの重要なポイントを深掘りします。
まず、dfs で depth[] と parent[] を事前に計算しています。 これにより、各ノードの深さと親が分かる状態になっています。
lca(u, v) の中では、 while (depth[u] > depth[v]) で「u の方が深いなら親に上げる」、 while (depth[v] > depth[u]) で「v の方が深いなら親に上げる」、 という形で、深さを揃えています。
その後、while (u != v) で、 u と v を同時に親に上げていき、 同じノードになったところでループを抜けます。 そのノードが LCA です。
この素朴な方法は、 距離計算の理解を深めるうえで非常に分かりやすく、 ノード数がそれほど大きくない場合には実用的でもあります。
LCAの高速化と距離計算のスケール感
競技プログラミングや大規模なシステムでは、 ノード数が数十万、クエリ数が数十万という規模で 距離計算を行うことがあります。
その場合、素朴なLCAでは 「毎回親に上がる回数」が深さに比例してしまい、 全体として遅くなる可能性があります。
そこで登場するのが、 二分木ジャンプ（Binary Lifting）や Euler Tour + RMQ（Range Minimum Query） といった高速なLCAアルゴリズムです。
これらは、 事前に「親を2^kステップ分まとめて持つテーブル」を作ったり、 木を一次元の列に展開して「最小深さの位置」を高速に求めたりすることで、 LCAを O(1) または O(log N) で求められるようにします。
初心者の段階では、 「LCAを高速に求める方法がある」 「距離計算は、LCAが高速に求まれば大量のクエリにも耐えられる」 というスケール感だけを押さえておくと十分です。
重要なのは、 距離計算が「深さ＋LCA」という構造を持っていることを理解し、 必要に応じて高速なLCAアルゴリズムを学べる状態になっておくことです。
距離計算と木DP・グラフ探索とのつながり
木構造の距離計算は、 木DPやグラフ探索と深くつながっています。
木DPでは、「各ノードを根とする部分木に対して何らかの値を定義し、 子の値を使って親の値を計算する」という形で、 部分木ごとの集計を行います。
距離計算も、 「深さ」という形で根からの距離を持ち、 「LCA」という形で共通祖先を扱うことで、 ノード間の関係を定量的に捉えています。
グラフ探索（特に木上のDFS／BFS）は、 深さや親を求めるための基盤です。 距離計算は、その上に乗る「応用レイヤー」として位置づけられます。
このように、 木構造の距離計算を理解すると、 木DP・グラフ探索・LCAといったアルゴリズムが 一つの連続した世界として見えてきます。
それは、単なる「テクニックの寄せ集め」ではなく、 「階層構造をどう数値で捉えるか」という 一貫した視点につながっていきます。
セキュリティ・パフォーマンスの観点から見る距離計算
距離計算は、ネットワーク構造や権限構造の解析にも使われます。 そのため、セキュリティの観点からもいくつか注意点があります。
まず、外部入力から渡された木構造に対して 無制限に DFS を行い、深さや親を計算すると、 攻撃者が「極端に深い木」や「極端に大きな木」を送ることで、 スタックの枯渇や計算時間の増大を引き起こす可能性があります。
また、木だと思っていた構造にサイクルが紛れ込んでいると、 DFS が終わらなくなり、 距離計算の前提そのものが崩れます。
安全な設計としては、
ノード数や深さに上限を設ける 入力構造を検証し、サイクルがないことを確認する 必要に応じて再帰ではなく非再帰（自前スタック）でDFSを行う 距離計算のクエリ数に対して、アルゴリズムの計算量を見積もる
といった視点が重要になります。
距離計算は「便利な道具」であると同時に、 入力の形やアルゴリズムの特性を理解していないと パフォーマンスやセキュリティの落とし穴にもなり得ます。
後半のまとめ
後半では、木構造の距離計算を一段深く理解するために
LCAを使った距離の公式 の意味 具体的な距離計算の例 素朴なLCAアルゴリズムのJava実装 LCA高速化と距離計算のスケール感 距離計算と木DP・グラフ探索とのつながり セキュリティ・パフォーマンスの観点から見た距離計算の注意点
を整理しました。
木構造の距離計算を自分のものにできると、 階層構造を持つあらゆるデータに対して 「どれくらい離れているか」を数値で捉え、 設計や解析に活かせるようになります。 それは、アルゴリズムの知識を「現場で使える武器」に変えていく大きな一歩です。