木の直径(重み付き)
(tree/diameter_weighted.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

重み付き木の直径長とその両端点を $O(N)$ で求める。

できること

• pair<T, pair<int, int>> tree_diameter_weighted(const vector<vector<pair<int, T>>> &g) 直径を返す。戻り値の first は重み和としての直径長、second.first と second.second は両端点

使い方

隣接リストを vector<vector<pair<int, T>>> で持ち、tree_diameter_weighted(g) を呼ぶ。

vector<vector<pair<int, long long>>> g(n);
g[u].push_back({v, w});
g[v].push_back({u, w});

auto [dist, ends] = tree_diameter_weighted(g);
int s = ends.first;
int t = ends.second;

重みなし木には diameter.cpp の tree_diameter を使う。

実装上の補足

任意の頂点から最遠点 s を取り、さらに s から最遠点を取る 2 回 DFS で求める。 木を仮定しているので、連結で閉路のないグラフに対して使う。

Verified with

• test/aoj_grl_5_a_diameter.test.cpp
• test/yosupo_tree_diameter.test.cpp

Code

template<class T>
pair<T, pair<int, int>> tree_diameter_weighted(const vector<vector<pair<int, T>>> &G) {
    int n = G.size();
    if (n == 0) return {T(), {-1, -1}};

    vector<T> dist(n);
    int far = 0;
    auto dfs = [&](int v, int p, auto &&f) -> void {
        for (auto &&e : G[v]) {
            int to = e.first;
            T cost = e.second;
            if (to == p) continue;
            dist[to] = dist[v] + cost;
            if (dist[far] < dist[to]) far = to;
            f(to, v, f);
        }
    };

    dist[0] = T();
    dfs(0, -1, dfs);
    int s = far;
    dist[s] = T();
    dfs(s, -1, dfs);
    return {dist[far], {s, far}};
}

/**
 * @brief 木の直径(重み付き)
 */

#line 1 "tree/diameter_weighted.cpp"
template<class T>
pair<T, pair<int, int>> tree_diameter_weighted(const vector<vector<pair<int, T>>> &G) {
    int n = G.size();
    if (n == 0) return {T(), {-1, -1}};

    vector<T> dist(n);
    int far = 0;
    auto dfs = [&](int v, int p, auto &&f) -> void {
        for (auto &&e : G[v]) {
            int to = e.first;
            T cost = e.second;
            if (to == p) continue;
            dist[to] = dist[v] + cost;
            if (dist[far] < dist[to]) far = to;
            f(to, v, f);
        }
    };

    dist[0] = T();
    dfs(0, -1, dfs);
    int s = far;
    dist[s] = T();
    dfs(s, -1, dfs);
    return {dist[far], {s, far}};
}

/**
 * @brief 木の直径(重み付き)
 */

Back to top page