結果

問題 No.3113 The farthest point
コンテスト
ユーザー Nzt3
提出日時 2025-04-15 15:36:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 328 ms / 2,000 ms
コード長 1,036 bytes
コンパイル時間 3,553 ms
コンパイル使用メモリ 294,992 KB
実行使用メモリ 33,256 KB
最終ジャッジ日時 2025-04-15 15:36:34
合計ジャッジ時間 9,772 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

bool chmax(ll &a,ll b){
  if(a<b){
    a=b;
    return 1;
  }
  return 0;
}
int main(){
  int N;
  cin>>N;
  using edge = pair<int,ll>;
  vector G(N,vector<edge>());
  for(int i=0;i<N-1;i++){
    int U,V;
    ll C;
    cin>>U>>V>>C;
    --U,--V;
    G[U].push_back(edge{V,C});
    G[V].push_back(edge{U,C});
  }

  vector d(N,-1),p(N,-1);
  vector pw(N,0ll);
  vector child(N,vector<ll>());
  stack<int>dfs;
  dfs.push(0);
  ll ans=0;
  while(dfs.size()){
    int v=dfs.top();
    dfs.pop();
    for(int &i=++d[v];i<G[v].size();i++){
      auto [v2,w]=G[v][i];
      if(v2!=p[v]){
        dfs.push(v);
        dfs.push(v2);
        p[v2]=v;
        pw[v2]=w;
        break;
      }
    }
    if(d[v]==G[v].size()){
      auto &c=child[v];
      c.push_back(0);
      sort(c.begin(),c.end(),greater<ll>());
      if(c.size()>=2){
        chmax(ans,c[0]+c[1]);
      }
      if(p[v]!=-1){
        child[p[v]].push_back(c[0]+pw[v]);
      }
    }
  }
  cout<<ans<<'\n';
}
0