結果

問題 No.3113 The farthest point
ユーザー Today03
提出日時 2025-04-18 21:13:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 364 ms / 2,000 ms
コード長 2,094 bytes
コンパイル時間 3,267 ms
コンパイル使用メモリ 283,692 KB
実行使用メモリ 29,540 KB
最終ジャッジ日時 2025-04-18 21:13:44
合計ジャッジ時間 9,065 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define ALL(x) (x).begin(),(x).end()
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
#define LB(v, x) (ll)(lower_bound(ALL(v),x)-(v).begin())
#define UQ(v) sort(ALL(v)),(v).erase(unique(ALL(v)),v.end())
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i, a, b) for(ll i=(ll)(a); (a)<(b) ? i<(b) : i>(b); i+=((a)<(b) ? 1 : -1))
#define chmax(a, b) ((a)<(b) ? ((a)=(b), 1) : 0)
#define chmin(a, b) ((a)>(b) ? ((a)=(b), 1) : 0)

template<typename T> using rpriority_queue=priority_queue<T,vector<T>,greater<T>>;
using ll=long long; const int INF=1e9+10; const ll INFL=4e18; using ld=long double; using ull=uint64_t;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;



int main(){
    int N; cin>>N;
    WG G(N);
    REP(i,N-1){
        ll u,v,w; cin>>u>>v>>w; u--,v--;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }

    VVL dp1(N);
    auto dfs1=[&](auto&& dfs, int now, int pre)-> ll {
        int M=G[now].size();
        dp1[now]=VL(M,-INFL);

        REP(i,M){
            auto [to,w]=G[now][i];
            if(to==pre) continue;
            dp1[now][i]=max(dp1[now][i],dfs(dfs,to,now)+w);
        }

        ll ret=-INFL;
        REP(i,M) chmax(ret,dp1[now][i]);

        if(ret==-INFL) ret=0;
        return ret;
    };

    ll ans=-INFL;
    auto dfs2=[&](auto&& dfs2, int now, int pre, ll d)-> void {
        int M=G[now].size();
        if(pre!=-1){
            REP(i,M)if(G[now][i].first==pre) dp1[now][i]=d;
        }

        VL dp_left(M+1,-INFL), dp_right(M+1,-INFL);
        REP(i,M) dp_left[i+1]=max(dp_left[i],dp1[now][i]);
        FOR(i,M-1,-1) dp_right[i]=max(dp_right[i+1],dp1[now][i]);

        REP(i,M){
            auto [to,w]=G[now][i];
            if(to==pre) continue;
            dfs2(dfs2,to,now,max({0ll,dp_left[i],dp_right[i+1]})+w);
        }

        chmax(ans,dp_left[M]);
    };

    dfs1(dfs1,0,-1);
    dfs2(dfs2,0,-1,0);

    cout<<max(ans,0ll)<<endl;
}
0