結果

問題 No.3113 The farthest point
ユーザー Nzt3
提出日時 2025-04-15 15:40:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 1,231 bytes
コンパイル時間 3,640 ms
コンパイル使用メモリ 288,008 KB
実行使用メモリ 24,428 KB
最終ジャッジ日時 2025-04-15 15:41:05
合計ジャッジ時間 7,885 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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() {
  cin.tie(0)->sync_with_stdio(0);
  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);
  using al2 = array<ll, 2>;
  vector child(N, al2{0, -1});
  auto top2 = [](al2 &a, ll v) {
    if (v > a[0]) {
      a[1] = a[0];
      a[0] = v;
    } else if (v > a[1]) {
      a[1] = v;
    }
  };
  stack<int, vector<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];
      chmax(ans, c[0] + c[1]);
      if (p[v] != -1) {
        top2(child[p[v]], c[0] + pw[v]);
      }
    }
  }
  cout << ans << '\n';
}
0