結果

問題 No.3113 The farthest point
ユーザー MZKi
提出日時 2025-04-19 00:24:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 366 ms / 2,000 ms
コード長 3,720 bytes
コンパイル時間 4,626 ms
コンパイル使用メモリ 262,160 KB
実行使用メモリ 31,044 KB
最終ジャッジ日時 2025-04-19 00:24:21
合計ジャッジ時間 11,089 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<atcoder/all>
using namespace atcoder;

#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define eps (double)(1e-9)
#define pi (double) acos(-1)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

struct Rerooting {
    /* start 問題ごとに書き換え */
    //下の選択も変更
    struct Edge { //辺の型
        ll to, cost;
        Edge(ll to_, ll cost_) : to(to_), cost(cost_) {}
    };
    struct DP {  // DP の型
        long long dp;
        DP(long long dp_) : dp(dp_) {}
    };
    const DP identity = DP(0);  // 単位元(末端の値は add_root(identity) になるので注意)

    //merge済み+1つ
    function<DP(DP, DP, Edge)> merge1 = [](DP dp_cum, DP d, Edge e) -> DP {
        return DP(max(dp_cum.dp, d.dp + e.cost));
    };
    //merge済み + merge済み
    function<DP(DP, DP)> merge2 = [](DP dp_cum, DP d) -> DP {
        return DP(max(dp_cum.dp, d.dp));
    };
    function<DP(DP, int)> add_root = [](DP d, int v) -> DP {
        return d;
    };
    /* end 問題ごとに書き換え */
    // グラフの定義
    using Graph = vector<vector<Edge>>;
    vector<vector<DP>> dp;  // dp[v][i]: vから出るi番目の有向辺に対応する部分木のDP
    vector<DP> ans;         // ans[v]: 頂点vを根とする木の答え
    Graph G;
    Rerooting(int N) : G(N) {
        dp.resize(N);
        ans.assign(N, identity);
    }
    void add_edge(int a, Edge b) {
        G[a].push_back({b});
    }
    void build() {
        dfs(0);            // 普通に木DP
        bfs(0, identity);  // 残りの部分木に対応するDPを計算
    }
    DP dfs(int v, int p = -1) {  // 頂点v, 親p
        DP dp_cum = identity;
        int deg = G[v].size();
        dp[v] = vector<DP>(deg, identity);
        for (int i = 0; i < deg; i++) {
            int u = G[v][i].to;
            if (u == p) continue;
            dp[v][i] = dfs(u, v);
            dp_cum = merge1(dp_cum, dp[v][i], G[v][i]);
        }
        return add_root(dp_cum, v);
    }
    void bfs(int v, const DP& dp_p, int p = -1) {  // bfs だが、実装が楽なので中身は dfs になっている
        int deg = G[v].size();
        for (int i = 0; i < deg; i++) {  // 前のbfsで計算した有向辺に対応する部分木のDPを保存
            if (G[v][i].to == p) dp[v][i] = dp_p;
        }
        vector<DP> dp_l(deg + 1, identity), dp_r(deg + 1, identity);  // 累積merge
        for (int i = 0; i < deg; i++) {
            dp_l[i + 1] = merge1(dp_l[i], dp[v][i], G[v][i]);
        }
        for (int i = deg - 1; i >= 0; i--) {
            dp_r[i] = merge1(dp_r[i + 1], dp[v][i], G[v][i]);
        }

	//どちらか選択
        ans[v] = add_root(dp_l[deg], v);  // 頂点 v の答え
	//ここまで
        for (int i = 0; i < deg; i++) {  // 一つ隣の頂点に対しても同様に計算
            int u = G[v][i].to;
            if (u == p) continue;
            bfs(u, add_root(merge2(dp_l[i], dp_r[i + 1]), v), v);
        }
    }
};



int main() {
    int n;
    cin >> n;
    Rerooting reroot(n);
    rep(i, n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;

        reroot.add_edge(u, {v, w});
        reroot.add_edge(v, {u, w});
    }

    reroot.build();

    ll ans = -inf;
    rep(i, n)chmax(ans, reroot.ans[i].dp);

    cout << ans << endl;
}
0