結果

問題 No.3113 The farthest point
ユーザー Tatsu_mr
提出日時 2025-04-19 18:48:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 4,727 bytes
コンパイル時間 3,897 ms
コンパイル使用メモリ 300,068 KB
実行使用メモリ 18,036 KB
最終ジャッジ日時 2025-04-19 18:48:22
合計ジャッジ時間 7,917 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
#define SZ(v) ((int)(v).size())

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

struct SetupIo {
    SetupIo() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} setupio;

template <class T, T (*op)(T, T), T (*e)()>
struct DST {
    private:
    int n, h = 1, w;
    vector<vector<T>> table;
    vector<int> get;
    
    public:
    DST() {}
    DST(vector<T> &v) : n(v.size()) {
        while ((1 << h) < n) {
            h++;
        }
        int w = (1 << h);
        table.assign(h, vector<T>(w, e()));
        for (int i = 0; i < h; i++) {
            int len = (1 << (h - i - 1));
            for (int pos = (1 << (h - i - 1)) - 1; pos < w; pos += (len << 1)) {
                for (int j = pos; j >= pos - len + 1; j--) {
                    table[i][j] = (j == pos ? v[j] : op(v[j], table[i][j + 1]));
                }
                for (int j = pos + 1; j <= pos + len; j++) {
                    table[i][j] = (j == pos + 1 ? v[j] : op(table[i][j - 1], v[j]));
                }
            }
        }
        get.resize(w);
        for (int i = 1; i < w; i++) {
            get[i] = __builtin_clz(i) - (32 - h);
        }
    }
    
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) {
            return e();
        }
        if (r - l == 1) {
            return table[h - 1][l];
        }
        int i = get[l ^ (r - 1)];
        return op(table[i][l], table[i][r - 1]);
    }
};

lint op(lint a, lint b) { return max(a, b); }
lint e() { return 0; }

int main() {
    int n;
    cin >> n;
    vector<vector<pair<int, lint>>> g(n);
    rep(i, n - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    // v の部分木について,
    // 「葉 ~ v パスの長さの最大値 path(v)」と
    // 「v の部分木の任意の 2 頂点間の単純パスの重みの和の最大値 real(v)」
    // のペアを返す
    auto dfs = [&](auto dfs, int v, int pv) -> pair<lint, lint> {
        lint path = 0, real = 0;
        vector<lint> costs, paths, reals;
        for (auto [nv, w] : g[v]) {
            if (nv == pv) { continue; }
            auto [x, y] = dfs(dfs, nv, v);
            costs.emplace_back(w);
            paths.emplace_back(x);
            reals.emplace_back(y);
        }

        // 葉 ~ v パスの長さの最大値としてありえるもの
        // 1. v だけ（長さ 0 のパス）
        // 2. v -> nv パス（cost(v, nv)）
        // 3. 葉 ~ nv -> v パス（path(nv) + cost(nv, v)）

        // 2
        if (SZ(costs) >= 1) {
            path = max(path, *max_element(ALL(costs)));
        }
        // 3
        rep(i, SZ(paths)) {
            path = max(path, paths[i] + costs[i]);
        }

        // v の部分木についての最大値としてありえるもの
        // 上の 1 ~ 3
        // 4. nv の部分木についての最大値（real(nv)）
        // 5. nv1 -> v -> nv2 パス（cost(nv1, v) + cost(v, nv2)）
        // 6. 葉 ~ nv1 -> v -> nv2 パス（path(nv1) + cost(nv1, v) + cost(v, nv2)）
        // 7. 葉 ~ nv1 -> v -> nv2 ~ 葉 パス（path(nv1) + cost(nv1, v) + cost(v, nv2) + path(nv2)）

        // 1 ~ 3
        real = max(real, path);
        // 4
        if (SZ(reals) >= 1) {
            real = max(real, *max_element(ALL(reals)));
        }
        if (SZ(costs) >= 2) {
            // 5
            auto costs2 = costs;
            sort(rALL(costs2));
            real = max(real, costs[0] + costs[1]);
            // 6
            vector<lint> sums;
            rep(i, SZ(paths)) {
                sums.emplace_back(costs[i] + paths[i]);
            }
            DST<lint, op, e> Costs(costs);
            rep(i, SZ(paths)) {
                lint tmp = sums[i];
                tmp += max(Costs.prod(0, i), Costs.prod(i + 1, SZ(costs)));
                real = max(real, tmp);
            }
            // 7
            DST<lint, op, e> Sums(sums);
            rep(i, SZ(sums)) {
                lint tmp = sums[i];
                tmp += max(Sums.prod(0, i), Sums.prod(i + 1, SZ(sums)));
                real = max(real, tmp);
            }
        }
        
        return {path, real};
    };

    cout << dfs(dfs, 0, -1).second << "\n";
}
0