結果

問題 No.3113 The farthest point
コンテスト
ユーザー D M
提出日時 2026-02-04 09:32:43
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 6,177 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,643 ms
コンパイル使用メモリ 395,212 KB
実行使用メモリ 116,420 KB
最終ジャッジ日時 2026-02-04 09:33:12
合計ジャッジ時間 22,164 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, limit) for (long long i = (long long)x; i < (long long)limit; i++)
#define REP(i, x, limit) for (long long i = (long long)x; i <= (long long)limit; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el '\n'
#define spa " "
#define Yes cout << "Yes" << el
#define No cout << "No" << el
#define YES cout << "YES" << el
#define NO cout << "NO" << el
#define eps (1e-10)
#define Equals(a,b) (fabs((a) - (b)) < eps )
#define debug(x) cerr << #x << " = " << x << el
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using vb = vector<bool>;
const double pi = 3.141592653589793238;
const int inf = 1073741823;
const ll infl = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
const ll MOD = 998244353;
#include<atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using vm = vector<mint>;
// Requires: #include <atcoder/segtree>  (or <atcoder/all>)
// Also needs: <bits/stdc++.h>, using namespace std;

struct Edge { long long to, cost; };

struct S_rmq { long long value; long long index; };
S_rmq op_rmq(S_rmq a, S_rmq b){
  if(a.value < b.value) return a;
  else return b;
}
S_rmq E_rmq(){ return {(1LL << 60), -1LL}; }

struct S_rsq { long long value; };
S_rsq op_rsq(S_rsq a, S_rsq b){ return {a.value + b.value}; }
S_rsq E_rsq(){ return {0}; }

struct weighted_euler_tour {
  std::vector<long long> depth, visit, cost1, cost2;
  std::vector<long long> discover, finishing;
  std::vector<std::vector<Edge>> g;
  long long n;
  std::map<std::pair<long long, long long>, long long> edge_index1;
  std::map<std::pair<long long, long long>, long long> edge_index2;

  atcoder::segtree<S_rmq, op_rmq, E_rmq> rmq;
  atcoder::segtree<S_rsq, op_rsq, E_rsq> rsq1;
  atcoder::segtree<S_rsq, op_rsq, E_rsq> rsq2;

  weighted_euler_tour(long long n=1, std::vector<std::vector<Edge>> g=std::vector<std::vector<Edge>>()){
    init(n, g);
  }

  void init(long long n, std::vector<std::vector<Edge>> g){
    this->n = n;
    depth.clear();
    visit.clear();
    cost1.clear();
    cost2.clear();
    discover.assign(n, (1LL<<30));
    finishing.assign(n, -1);
    edge_index1.clear();
    edge_index2.clear();
    this->g = std::move(g);
    this->g.resize(n);
  }

  void add_edge(long long u, long long v, long long cost){
    g[u].push_back({v, cost});
    g[v].push_back({u, cost});
  }
  
  void dfs(long long root){
    // If you might call dfs() multiple times, clear these:
    // depth.clear(); visit.clear(); cost1.clear(); cost2.clear();
    cost1.push_back(0);
    cost2.push_back(0);
    Dfs(root, -1, 0);

    for(long long i=0;i<(long long)visit.size();i++){
      discover[visit[i]] = std::min(discover[visit[i]], i);
      finishing[visit[i]] = std::max(finishing[visit[i]], i+1);
    }

    std::vector<S_rmq> depth_v((int)depth.size());
    for(long long i=0; i<(long long)depth.size(); i++){
      depth_v[i] = {depth[i], visit[i]};
    }
    std::vector<S_rsq> cost1_v((int)cost1.size());
    for(long long i=0; i<(long long)cost1.size(); i++){
      cost1_v[i] = {cost1[i]};
    }
    std::vector<S_rsq> cost2_v((int)cost2.size());
    for(long long i=0; i<(long long)cost2.size(); i++){
      cost2_v[i] = {cost2[i]};
    }

    rmq  = atcoder::segtree<S_rmq, op_rmq, E_rmq>(depth_v);
    rsq1 = atcoder::segtree<S_rsq, op_rsq, E_rsq>(cost1_v);
    rsq2 = atcoder::segtree<S_rsq, op_rsq, E_rsq>(cost2_v);
  }

  void Dfs(long long v, long long p, long long d) {
    visit.push_back(v);
    depth.push_back(d);
    for (Edge u : g[v]) {
      if (u.to == p) continue;
      cost1.push_back(u.cost);
      cost2.push_back(u.cost);
      edge_index1[{std::min(v,u.to), std::max(v,u.to)}] = (long long)cost1.size()-1;
      edge_index2[{v, u.to}] = (long long)cost2.size()-1;

      Dfs(u.to, v, d + 1);

      visit.push_back(v);
      depth.push_back(d);
      cost1.push_back(0);
      cost2.push_back(-u.cost);
      edge_index2[{u.to, v}] = (long long)cost2.size()-1;
    }
  }

  long long lca(long long u, long long v){
    // FIX: segtree::prod is [l, r), so right end must be +1
    long long l = std::min(discover[u], discover[v]);
    long long r = std::max(discover[u], discover[v]) + 1;
    return rmq.prod(l, r).index;
  }

  long long pe(long long u){
    return rsq2.prod(0, discover[u]+1).value;
  }

  long long dist(long long u, long long v){
    if(u==v) return 0;
    return pe(u) + pe(v) - 2*pe(lca(u,v));
  }

  long long sum(long long x){
    return rsq1.prod(discover[x], finishing[x]).value;
  }

  void update(long long u, long long v, long long x){
    if(u > v) std::swap(u,v);
    if(edge_index1.find({u,v})==edge_index1.end()) return;
    rsq1.set(edge_index1[{u,v}], {x});
    
    // make u the shallower endpoint (parent) in the rooted tree
    if(depth[discover[u]] > depth[discover[v]]) std::swap(u,v);
    rsq2.set(edge_index2[{u,v}], {x});
    rsq2.set(edge_index2[{v,u}], {-x});
  }

  void add(long long u, long long v, long long x){
    if(u > v) std::swap(u,v);
    if(edge_index1.find({u,v})==edge_index1.end()) return;

    long long idx1 = edge_index1[{u,v}];
    rsq1.set(idx1, {rsq1.prod(idx1, idx1+1).value + x});

    // FIX: depth[] is indexed by Euler position; use depth[discover[*]]
    if(depth[discover[u]] > depth[discover[v]]) std::swap(u,v);

    long long idx_uv = edge_index2[{u,v}];
    long long idx_vu = edge_index2[{v,u}];
    rsq2.set(idx_uv, {rsq2.prod(idx_uv, idx_uv+1).value + x});
    rsq2.set(idx_vu, {rsq2.prod(idx_vu, idx_vu+1).value - x});
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;cin>>n;
  weighted_euler_tour wet(n);
  rep(i,0,n-1){
    ll u,v,w;
    cin>>u>>v>>w;
    u--;v--;
    wet.add_edge(u,v,w);
  }
  wet.dfs(0);
  ll stc=-infl,si=-1;
  rep(i,0,n){
    ll s=wet.dist(0,i);
    if(s>stc){
      stc=s;
      si=i;
    }
  }
  ll ans=-infl;
  rep(i,0,n){
    ll s=wet.dist(si,i);
    ans=max(ans,s);
  }
  cout<<ans<<el;
}
0