木の直径（Tree Diameter）

木における2頂点間のパスの長さの最大値を求める。

重みなしの木なら、BFSを2回行うことで O(V) で求められる。

特徴

項目	内容
用途	木の直径・最長パス
対象	重みなしの木
計算量	O(V)
空間計算量	O(V)

考え方

1. 任意の頂点 s からBFSし、最も遠い頂点 a を求める。
2. a からBFSし、最も遠い頂点 b を求める。
3. a から b までの距離が木の直径となる。

2回目のBFSで親頂点を記録すれば、直径をなすパスも復元できる。

実装

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> dist(n), parent(n);
    auto bfs = [&](int s) -> int {
        fill(dist.begin(), dist.end(), -1);
        fill(parent.begin(), parent.end(), -1);
        queue<int> q;
        dist[s] = 0;
        q.push(s);
        int far = s;

        while (!q.empty()) {
            int v = q.front(); q.pop();
            if (dist[v] > dist[far]) far = v;
            for (int nv : g[v]) {
                if (dist[nv] != -1) continue;
                dist[nv] = dist[v] + 1;
                parent[nv] = v;
                q.push(nv);
            }
        }
        return far;
    };

    int a = bfs(0);
    int b = bfs(a);
    int diameter = dist[b];

    // 直径をなすパスを復元
    vector<int> path;
    for (int v = b; v != -1; v = parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());

    cout << diameter << '\n';
    for (int v : path) cout << v << ' ';
    cout << '\n';
}

使用例

入力（0-indexed、無向木）

5
0 1
1 2
1 3
3 4

出力例

3
4 3 1 0

直径の長さは3。 経路は 4 → 3 → 1 → 0。

注意点

• 2回のBFSで直径を求められるのは木の性質によるもの。一般グラフでは成立しない。
• 重みなしの場合、直径は辺の本数で数える。
• 頂点数で数えたい場合は、直径の長さに1を加える。
• 最遠頂点が複数ある場合、どれを選んでもよい。
• 直径をなすパスは一意とは限らない。
• 重み付き木でも、辺重みが非負なら2回の探索で求められる。距離は辺重みの合計で管理する。
• 負の辺重みを許す場合は、一般には2回探索の方法を使えない。

関連

• BFS
• DFS
• LCA
• 木DP