#1075603 (C++23) No.3113 The farthest point

提出ソース
結果

問題	No.3113 The farthest point
ユーザー	rogi52
提出日時	2025-04-18 23:18:27
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	379 ms / 2,000 ms
コード長	15,029 bytes
コンパイル時間	4,441 ms
コンパイル使用メモリ	313,840 KB
実行使用メモリ	77,056 KB
最終ジャッジ日時	2025-04-18 23:18:39
合計ジャッジ時間	10,511 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 33
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp"
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f32 = double;
using f64 = long double;
using f128 = __float128;

#define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl;

#define FOR1(n)          for(int _ =  0 , n_ = (n); _ < n_; _++)
#define FOR2(i, n)       for(int i =  0 , n_ = (n); i < n_; i++)
#define FOR3(i, s, t)    for(int i = (s), t_ = (t); i < t_; i++)
#define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_)
#define OVERLOAD4(a, b, c, d, e, ...) e
#define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define REV1(n)          for(int _ = (n) - 1; _ >=  0 ; _--)
#define REV2(i, n)       for(int i = (n) - 1; i >=  0 ; i--)
#define REV3(i, s, t)    for(int i = (t) - 1, s_ = (s); i >= s_; i--)
#define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_)
#define OVERLOAD3(a, b, c, d, ...) d
#define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__)

#define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_))

#define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&]

template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >;
template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>;

template < class T, class U > bool chmin(T& a, const U& b) { return a > b ? a = b, 1 : 0; }
template < class T, class U > bool chmax(T& a, const U& b) { return a < b ? a = b, 1 : 0; }

i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) <  0 && n % d != 0); }
i64  ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); }

template < class T, class F > T bin_search(T ok, T ng, F check) { while(abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class F > T bin_search_real(T ok, T ng, F check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }

template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); }
template < class T > pair< T, int > min(const vector< T >& a) { auto itr = min_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > pair< T, int > max(const vector< T >& a) { auto itr = max_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); }
template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); }
template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); }
void sort(string& s) { sort(s.begin(), s.end()); }
void rsort(string& s) { sort(s.rbegin(), s.rend()); }
void reverse(string& s) { reverse(s.begin(), s.end()); }
template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); }
template < class T > int LB(vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); }
template < class T > int UB(vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); }
template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; }

istream& operator >> (istream& is, i128& x) {
    string s; is >> s;
    int m = (s[0] == '-');
    x = 0;
    FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0');
    if(m) x *= -1;
    return is;
}
ostream& operator << (ostream& os, const i128& x) {
    if(x == 0) return os << '0';
    i128 y = x; if(y < 0) { os << '-'; y *= -1; }
    vector<int> ny;
    while(y) ny.push_back(y % 10), y /= 10;
    REV(i, ssize(ny)) os << ny[i];
    return os;
}
namespace scan {
struct x0 { template < class T > operator T() { T x; cin >> x; return x; } };
struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } };
struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } };
struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance;
}
scan::x0 in() { return scan::x0(); }
scan::x1 in(int n) { return scan::x1(n); }
scan::x2 in(int h, int w) { return scan::x2(h, w); }

template < class T > ostream& operator << (ostream& os, const vector< T > a) {
    const int n = a.size();
    FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; }
    return os;
}
template < class T > int print_n(const vector< T > a) { for(T x : a) cout << x << '\n'; return 0; }
int print() { cout << '\n'; return 0; }
template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); }
namespace printer {
    void prec(int n) { cout << fixed << setprecision(n); }
    void flush() { cout.flush(); }
}

constexpr pair<int, int> dir4[] = {{-1, 0}, {0, -1}, {+1, 0}, {0, +1}};

vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; }
vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; }
vector<int>  operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; }
vector<int>  operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; }

template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; }
vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; }
template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; }

int YESNO(bool yes) { return print(yes ? "YES" : "NO"); }
int YesNo(bool yes) { return print(yes ? "Yes" : "No"); }

constexpr i32 INF32 = 1e9;
constexpr i64 INF64 = 1e18;
#line 2 "a.cpp"

template < class T >
struct tree_graph {
    int n;
    struct edge {
        int from, to, id; T cost;
    };
    std::vector<std::vector< edge >> g, g_org;
    tree_graph(int n) : n(n), g(n), g_org(n) {}

    void add_edge(int u, int v, int i = 0, T c = 1) {
        g[u].push_back(edge{u, v, i, c});
        g[v].push_back(edge{v, u, i, c});
        g_org[u].push_back(edge{u, v, i, c});
        g_org[v].push_back(edge{v, u, i, c});
    }

    std::pair< std::pair<int,int>, T > diameter() {
        std::vector< T > dist(n);
        std::function<void(int,int)> dfs = [&](int v, int p) -> void {
            for(auto [to, c] : g[v]) if(to != p) {
                dist[to] = dist[v] + c;
                dfs(to, v);
            }
        };
        dist[0] = 0; dfs(0, -1);
        int u = max_of(dist).key;
        dist[u] = 0; dfs(u, -1);
        auto [v, d] = max_of(dist);
        return {{u, v}, d};
    }

    std::vector<int> path(int u, int v) {
        std::vector<int> parent(n, -1);
        std::function<void(int,int)> dfs = [&](int v, int p) -> void {
            parent[v] = p;
            for(auto e : g[v]) if(e.to != p) dfs(e.to, v);
        };
        dfs(v, -1);
        std::vector<int> res;
        while(u != -1) res.push_back(u), u = parent[u];
        return res;
    }

    int id, root, heavy_light_decomposed;
    std::vector<int> size, depth, down, up, nxt, par, tour;

    void heavy_light_decomposition(int root = 0) {
        id = 0;
        this->root = root;
        size .assign(n, 0);
        depth.assign(n, 0);
        down.assign(n, -1);
        up  .assign(n, -1);
        tour.assign(n, -1);
        nxt.assign(n, root);
        par.assign(n, root);
        dfs_size(root);
        dfs_hld(root);
        heavy_light_decomposed = 1;
    }

    void dfs_size(int v) {
        size[v] = 1;
        for(auto& e : g[v]) {
            if(e.to == par[v]) {
                if(int(g[v].size()) >= 2 and e.to == g[v][0].to) {
                    std::swap(g[v][0], g[v][1]);
                } else continue;
            }
            depth[e.to] = depth[v] + 1;
            par[e.to] = v;
            dfs_size(e.to);
            size[v] += size[e.to];
            if(size[e.to] > size[g[v][0].to]) std::swap(e, g[v][0]);
        }
    }
    void dfs_hld(int v) {
        down[v] = id++;
        tour[down[v]] = v;
        for(auto e : g[v]) if(e.to != par[v]) {
            nxt[e.to] = (e.to == g[v][0].to ? nxt[v] : e.to);
            dfs_hld(e.to);
        }
        up[v] = id;
    }

    std::vector<std::pair<int,int>> ascend(int u, int v) {
        assert(heavy_light_decomposed);
        std::vector<std::pair<int,int>> res;
        while(nxt[u] != nxt[v]) res.push_back({down[u] + 1, down[nxt[u]]}), u = par[nxt[u]];
        if(u != v) res.push_back({down[u] + 1, down[v] + 1});
        return res;
    }
    std::vector<std::pair<int,int>> descend(int u, int v) {
        assert(heavy_light_decomposed);
        if(u == v) return {};
        if(nxt[u] == nxt[v]) return {{down[u] + 1, down[v] + 1}};
        std::vector<std::pair<int,int>> res = descend(u, par[nxt[v]]);
        res.push_back({down[nxt[v]], down[v] + 1});
        return res;
    }
    std::pair<int,int> idx(int v) { 
        assert(heavy_light_decomposed);
        return {down[v], up[v]};
    }

    template < class func >
    void path_query_comm(int u, int v, bool vertex, const func& f) {
        assert(heavy_light_decomposed);
        int x = lca(u, v);
        for(auto [a, b] : ascend(u, x)) {
            std::tie(a, b) = std::minmax({a, b});
            f(a, b);
        }
        if(vertex) f(down[x], down[x] + 1);
        for(auto [a, b] : descend(x, v)) {
            std::tie(a, b) = std::minmax({a, b});
            f(a, b);
        }
    }
    template < class func >
    void path_query(int u, int v, bool vertex, const func& f) {
        assert(heavy_light_decomposed);
        int x = lca(u, v);
        for(auto [a, b] : ascend(u, x)) f(a, b);
        if(vertex) f(down[x], down[x] + 1);
        for(auto [a, b] : descend(x, v)) f(a, b);
    }
    template < class func >
    void subtree_query(int v, bool vertex, const func& f) {
        assert(heavy_light_decomposed);
        f(down[v] + !vertex, up[v]);
    }
    int parent(int v) {
        assert(heavy_light_decomposed);
        return v == root ? -1 : par[v];
    }
    int la(int v, int d) {
        assert(heavy_light_decomposed);
        while(v != -1) {
            int u = nxt[v];
            if(down[v] - d >= down[u]) return tour[down[v] - d];
            d -= down[v] - down[u] + 1;
            v = parent(u);
        }
        return v;
    }
    int lca(int u, int v) {
        assert(heavy_light_decomposed);
        while(nxt[u] != nxt[v]) {
            if(down[u] < down[v]) std::swap(u, v);
            u = par[nxt[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }
    int dist(int u, int v) {
        assert(heavy_light_decomposed);
        return depth[u] + depth[v] - depth[lca(u, v)] * 2;
    }
    int jump(int u, int v, int d) {
        assert(heavy_light_decomposed);
        int x = lca(u, v);
        if(d <= depth[u] - depth[x]) return la(u, d);
        d -= depth[u] - depth[x];
        if(d <= depth[v] - depth[x]) return la(v, depth[v] - depth[x] - d);
        return -1;
    }
    int in_subtree(int r, int v) {
        return down[r] < down[v] and up[v] <= up[r];
    }
};

template < class S, class TREE, class EE, class EV, class VP, class I >
struct dp_on_tree {
    TREE& tree;
    
    std::vector< S > dp, dp_rev, answer;
    std::vector<std::vector< S >> dp_sub;
    EE f_ee;
    EV f_ev;
    VP f_vp;
    I id;
    int root;
    dp_on_tree(TREE& tree, const EE f_ee, const EV f_ev, const VP f_vp, const I id) : tree(tree), f_ee(f_ee), f_ev(f_ev), f_vp(f_vp), id(id) {}
    
    void solve(int root) {
        this->root = root;
        dp.assign(tree.n, id());
        dp_sub.resize(tree.n);
        FOR(v, tree.n) dp_sub[v].resize(tree.g_org[v].size());
        std::function<S(int,int)> dfs = [&](int v, int p) -> S {
            FOR(i, ssize(tree.g_org[v])) {
                auto e = tree.g_org[v][i];
                if(e.to != p) {
                    dp_sub[v][i] = dfs(e.to, v);
                    dp[v] = f_ee(dp[v], f_ev(dp_sub[v][i], e.id));
                }
            }
            return dp[v] = f_vp(dp[v], v);
        }; dfs(root, -1);
    }

    void reroot() {
        tree.heavy_light_decomposition(root);
        auto g = tree.g_org;
        dp_rev.assign(tree.n, id());
        std::function<void(int,int,S)> dfs = [&](int v, int p, S s) -> void {
            FOR(i, ssize(g[v])) {
                auto e = g[v][i];
                if(e.to == p) dp_sub[v][i] = s;
            }
            std::vector< S > R(g[v].size() + 1u);
            R[g[v].size()] = id();
            REV(i, ssize(g[v])) {
                auto e = g[v][i];
                R[i] = f_ee(R[i + 1], f_ev(dp_sub[v][i], e.id));
            }
            S L = id();
            FOR(i, ssize(g[v])) {
                auto e = g[v][i];
                if(e.to != p) {
                    dfs(e.to, v, f_vp(f_ee(L, R[i + 1]), v));
                }
                dp_rev[e.to] = f_vp(f_ee(L, R[i + 1]), v);
                L = f_ee(L, f_ev(dp_sub[v][i], e.id));
            }
        }; dfs(root, -1, id());
        
        answer.assign(tree.n, id());
        FOR(v, tree.n) {
            FOR(i, ssize(g[v])) {
                auto e = g[v][i];
                answer[v] = f_ee(answer[v], f_ev(dp_sub[v][i], e.id));
            }
            answer[v] = f_vp(answer[v], v);
        }
    }

    S get(int root, int v) {
        if(root == v) return answer[v];
        if(not tree.in_subtree(root, v)) return dp[v];
        return dp_rev[tree.jump(v, root, 1)];
    }
};

int main() {
    int N = in();
    tree_graph<i64> T(N);
    vector<int> W(N - 1);
    FOR(i, N - 1) {
        int u = in(), v = in(), w = in(); u--, v--;
        T.add_edge(u, v, i, w);
        W[i] = w;
    }
    auto f_ee = [&](i64 x, i64 y) { return max(x, y); };
    auto f_ev = [&](i64 x, int e_id) { return x + W[e_id]; };
    auto f_vp = [&](i64 x, int v_id) { return x; };
    auto id = [&]() { return 0; };
    dp_on_tree<i64, tree_graph<i64>, decltype(f_ee), decltype(f_ev), decltype(f_vp), decltype(id)> dp(T, f_ee, f_ev, f_vp, id);
    dp.solve(0);
    dp.reroot();
    i64 ans = 0;
    FOR(v, N) chmax(ans, dp.get(v, v));
    print(ans);
}
yukicoder

結果

ソースコード
