結果

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

ソースコード

diff # 

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

const long long INF = 1e18;
using ll = long long;


struct VertexAddSubtreeSum {
    int n;
    vector<vector<int>> edge;
    vector<int> et, et1, et2, de, l, et1s;

    VertexAddSubtreeSum(int n, vector<vector<int>> edge): n(n), edge(edge) {
        vector<int> P(n, -1), Q;
        Q.push_back(-0-1);
        Q.push_back(0);
        int ct = -1, depth = -1;
        et1.assign(n, 0);
        et2.assign(n, 0);
        de.assign(n, 0);

        while (!Q.empty()) {
            int i = Q.back(); Q.pop_back();
            if (i < 0) {
                ct++;
                et.push_back(i);
                et2[-i-1] = ct;
                depth--;
                continue;
            }
            et.push_back(i);
            ct++;
            if (et1[i] == 0) et1[i] = ct;
            depth++;
            de[i] = depth;
            for (int j = edge[i].size() - 1; j >= 0; j--) {
                int a = edge[i][j];
                if (a != P[i]) {
                    P[a] = i;
                    edge[a].erase(remove(edge[a].begin(), edge[a].end(), i), edge[a].end());
                    Q.push_back(-a-1);
                    Q.push_back(a);
                }
            }
        }
        l.resize(n);
        iota(l.begin(), l.end(), 0);
        sort(l.begin(), l.end(), [&](int x, int y) {
            return et1[x] < et1[y];
        });
        et1s = et1;
        sort(et1s.begin(),et1s.end());
        
    }

    pair<int, int> subtree(int x) {
        int left = et1[x], right = et2[x];
        int lft = lower_bound(et1s.begin(), et1s.end(), left) - et1s.begin();
        int rgt = lower_bound(et1s.begin(), et1s.end(), right) - et1s.begin();
        return {lft, rgt};
    }
};

ll op(ll x,ll y){return max(x,y);}
ll e(){return -1LL<<60;}
ll op2(ll x,ll y){return x+y;}
ll id(){return 0;}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> edge(n);
    unordered_map<long long, long long> cc;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        u--; v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
        cc[1LL * u * n + v] = w;
        cc[1LL * v * n + u] = w;
    }

    // BFS
    vector<long long> dist(n, INF), dist2(n, 0);
    vector<int> p(n, -1);
    deque<int> dq;
    dq.push_back(0);
    dist[0] = 0;

    while (!dq.empty()) {
        int now = dq.front(); dq.pop_front();
        for (int to : edge[now]) {
            if (dist[to] > dist[now] + 1) {
                dist[to] = dist[now] + 1;
                dist2[to] = dist2[now] + cc[1LL * to * n + now];
                dq.push_back(to);
                p[to] = now;
            }
        }
    }

    VertexAddSubtreeSum v1(n, edge);
    lazy_segtree<ll,op,e,ll,op2,op2,id> lst1(n);
    for (int i = 0; i < n; ++i) {
        lst1.set(i, dist2[v1.l[i]]);
    }

    vector<long long> a(n, -1);
    auto [l0, r0] = v1.subtree(0);
    for (int i : v1.et) {
        if (i >= 0) {
            if (i != 0) {
                long long cost = cc[1LL * p[i] * n + i];
                auto [l, r] = v1.subtree(i);
                lst1.apply(l, r, -2 * cost);
                lst1.apply(l0, r0, cost);
            }
            a[i] = lst1.all_prod();
        } else {
            int j = ~i;
            long long cost = cc[1LL * p[j] * n + j];
            auto [l, r] = v1.subtree(j);
            lst1.apply(l, r, 2 * cost);
            lst1.apply(l0, r0, -cost);
        }
    }

    cout << *max_element(a.begin(), a.end()) << endl;
    return 0;
}
0