木の直径（Tree Diameter）とは、木構造グラフにおいて最も離れた2つのノード間の距離を指します。この計算には、主に深さ優先探索（DFS）を2回行う方法と、動的計画法（DP）を用いる方法の2つが広く知られています。本記事では、それぞれのアルゴリズムの原理と実装手法について解説します。
DFSによる2回の探索アプローチ
この手法は非常に直感的で、計算量も効率的です。任意のノードから開始して最も遠いノードを見つけ、そのノードから再び最も遠いノードを探索するという2段階のプロセスで直径を求めます。
アルゴリズム：
- 木上の任意のノード
sを選択し、DFS（またはBFS）を行い、sから最も遠いノードuを見つけます。 - ノード
uから再びDFSを行い、uから最も遠いノードvを見つけます。 - ノード
uとvの間の距離が、この木の直径となります。
正当性の概要：
最初の探索で見つかったノード u は、必ず直径の端点の1つとなります。もし直径の端点でないと仮定すると、直径の定義および距離の三角形不等式（あるいは木構造の経路の一意性）に矛盾が生じます。したがって、端点 u から最も遠い点 v は直径のもう一方の端点となります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using Edge = pair<int, int>; // {destination, weight}
vector<vector<Edge>> adj;
vector<int> dist;
int farthest_node, max_distance;
// 深さ優先探索により、startノードから最も遠いノードと距離を特定する
void find_farthest(int current, int parent, int current_dist) {
dist[current] = current_dist;
if (current_dist > max_distance) {
max_distance = current_dist;
farthest_node = current;
}
for (const auto& edge : adj[current]) {
int next = edge.first;
int weight = edge.second;
if (next == parent) continue;
find_farthest(next, current, current_dist + weight);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
adj.resize(n + 1);
dist.resize(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
// 1回目の探索：適当なノード(ここでは1)から始める
max_distance = -1;
find_farthest(1, -1, 0);
int endpoint_u = farthest_node;
// 2回目の探索：見つかった端点から始める
max_distance = -1;
find_farthest(endpoint_u, -1, 0);
// 結果を出力
cout << max_distance << endl;
return 0;
}
動的計画法（Tree DP）によるアプローチ
この手法では、各ノードを「経路の頂点」と見なして、そのノードを通過する最長経路を計算します。木の根から葉に向かって探索（帰りがけ順）を行いながら、各ノードにおける最大値と2番目の最大値を管理します。
アルゴリズム：
各ノード i について、以下の2つの状態を定義します。
max_len[i]: ノードiを根とする部分木において、iから葉ノードへの最長距離。sec_len[i]: ノードiを根とする部分木において、iから葉ノードへの2番目に長い距離（ただし、最長パスと異なる経路）。
ノード i の子ノード j に対して、i から j への重みを w とすると、j からの経路長 path = max_len[j] + w を用いて以下の更新を行います。
pathが現在のmax_len[i]より大きい場合：sec_len[i]に旧max_len[i]を代入し、max_len[i]をpathで更新する。- そうでなく、
pathが現在のsec_len[i]より大きい場合：sec_len[i]をpathで更新する。
最終的な直径は、全ノードにおいて max_len[i] + sec_len[i] の最大値となります。これは、ノード i を折り返し点とする最長の経路を表しているためです。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using Edge = pair<int, int>; // {destination, weight}
vector<vector<Edge>> graph;
int diameter = 0;
// 指定したノードを根とする部分木の最長パス長を返し、全体の直径を更新する
int compute_diameter(int u, int parent) {
int max_1 = 0, max_2 = 0; // 1番目と2番目に長い経路
for (const auto& e : graph[u]) {
int v = e.first;
int w = e.second;
if (v == parent) continue;
int child_path = compute_diameter(v, u) + w;
// 最長経路と次長経路を更新
if (child_path > max_1) {
max_2 = max_1;
max_1 = child_path;
} else if (child_path > max_2) {
max_2 = child_path;
}
}
// このノードを通る経路の最大値（max_1 + max_2）で直径を更新
diameter = max(diameter, max_1 + max_2);
// 親ノードへは、このノードから伸びる最長経路を返す
return max_1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
graph.resize(n + 1);
for (int i = 0; i < m; ++i) {
int x, y, z;
cin >> x >> y >> z;
graph[x].emplace_back(y, z);
graph[y].emplace_back(x, z);
}
// 任意のノード（ここでは1）を根としてDPを開始
compute_diameter(1, -1);
cout << diameter << endl;
return 0;
}