library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/aoj/GRL_5_A.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_A"
#include <iostream>

#include "graph/tree_diameter.hpp"
int main() {
    int n;
    std::cin >> n;
    tree_diameter<long long> d(n);
    for (int i = 0; i < n - 1; i++) {
        int s, t;
        long long w;
        std::cin >> s >> t >> w;
        d.add_edge(s, t, w);
    }
    d.build();
    std::cout << d.length() << '\n';
}
#line 1 "test/aoj/GRL_5_A.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_A"
#include <iostream>

#line 2 "graph/tree_diameter.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
template <class T>
struct tree_diameter {
public:
    tree_diameter() : tree_diameter(0) {
    }
    explicit tree_diameter(int n) : _n(n), g(n) {
    }
    void add_edge(int u, int v, T w = 1) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    void build() {
        assert(_n >= 1);
        std::vector<int> par;
        std::vector<T> d;
        search(0, d, par);
        _u = int(std::ranges::max_element(d) - d.begin());
        search(_u, d, par);
        _v = int(std::ranges::max_element(d) - d.begin());
        _length = d[_v];
        _path.clear();
        for (int x = _v; x != -1; x = par[x]) _path.push_back(x);
        std::ranges::reverse(_path);
        for (int i = 0;; i++) {
            T pos = d[_path[i]];
            if (pos == _length - pos) {
                _center = {_path[i], _path[i]};
                break;
            }
            if (pos > _length - pos) {
                _center = {_path[i - 1], _path[i]};
                break;
            }
        }
    }
    T length() const {
        return _length;
    }
    std::pair<int, int> ends() const {
        return {_u, _v};
    }
    const std::vector<int>& path() const {
        return _path;
    }
    std::pair<int, int> center() const {
        return _center;
    }

private:
    int _n, _u = -1, _v = -1;
    std::pair<int, int> _center = {-1, -1};
    T _length = T(0);
    std::vector<std::vector<std::pair<int, T>>> g;
    std::vector<int> _path;
    void search(int s, std::vector<T>& d, std::vector<int>& par) const {
        d.assign(_n, T(0));
        par.assign(_n, -1);
        std::vector<int> st = {s};
        par[s] = s;
        while (!st.empty()) {
            int x = st.back();
            st.pop_back();
            for (auto [y, w] : g[x]) {
                if (par[y] != -1) continue;
                par[y] = x;
                d[y] = d[x] + w;
                st.push_back(y);
            }
        }
        par[s] = -1;
    }
};
#line 5 "test/aoj/GRL_5_A.test.cpp"
int main() {
    int n;
    std::cin >> n;
    tree_diameter<long long> d(n);
    for (int i = 0; i < n - 1; i++) {
        int s, t;
        long long w;
        std::cin >> s >> t >> w;
        d.add_edge(s, t, w);
    }
    d.build();
    std::cout << d.length() << '\n';
}
Back to top page