結果

問題 No.3113 The farthest point
ユーザー hot-cocoa
提出日時 2025-04-19 01:04:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,663 bytes
コンパイル時間 754 ms
コンパイル使用メモリ 81,120 KB
実行使用メモリ 32,040 KB
最終ジャッジ日時 2025-04-19 01:05:02
合計ジャッジ時間 6,446 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <limits>

using int64 = long long;

template<class T>
using Graph = std::vector<std::vector<T>>;

template<class T>
class Edge {
public:
    int to;
    T weight;
    Edge(int to, T weight) : to{to}, weight{weight} {}
};

template<class Weight>
class TreeDiameter {
    Graph<Edge<Weight>> g;
    using Result = std::pair<Weight, int>;

    Result dfs(int par, int curr)
    {
        Weight max_dist = std::numeric_limits<Weight>::min();
        int max_vertex = curr;
        bool has_child  = false;

        for (auto& e : g[curr]) {
            int to = e.to;
            Weight weight = e.weight;
            if (to == par) continue;

            auto [dist, vertex] = dfs(curr, to);
            Weight v = dist + weight;
            if (!has_child || v > max_dist) {
                has_child = true;
                max_dist = v;
                max_vertex = vertex;
            }
        }
        if (!has_child) {
            max_dist = 0;
            max_vertex = curr;
        }

        return {max_dist, max_vertex};
    }

public:
    TreeDiameter(const Graph<Edge<Weight>>& g) : g{g} {}

    Weight solve()
    {
        Result r = dfs(-1, 0);
        Result t = dfs(-1, r.second);
        return t.first;
    }
};

int main()
{
    int N;
    std::cin >> N;

    Graph<Edge<int64>> g(N);
    int64 u, v, w;
    for (int i = 0; i < N - 1; i++) {
        std::cin >> u >> v >> w;
        u--; v--;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    TreeDiameter<int64> tree(g);
    int64 res = tree.solve();
    std::cout << (res < 0 ? 0 : res) << std::endl;
    return 0;
}
0