結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>

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, int64>;

    Result dfs(int par, int curr)
    {
        Result ret(-1e18, curr);
        for (const auto& [to, weight] : g[curr]) {
            if (to == par)
                continue;

            Result t = dfs(curr, to);
            t.first += weight;
            ret = std::max(ret, t);
        }
        if (ret.first == -1e18)
            ret.first = 0;

        return ret;
    }

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);
    int u, v;
    int64 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);
    std::cout << tree.solve() << std::endl;
    return 0;
}
0