結果

問題 No.898 tri-βutree
コンテスト
ユーザー _____TAB_____
提出日時 2019-10-04 22:49:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,173 bytes
コンパイル時間 1,054 ms
コンパイル使用メモリ 82,404 KB
最終ジャッジ日時 2025-01-07 20:44:15
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
using namespace std;

void dfs(const vector<vector<pair<long long,int>>> &G, int v, int p, vector<int> &D){
  for(auto e : G[v]){
    long long w;
    int v_;
    tie(w,v_) = e;
    if(v_ == p) continue;
    D[v_] = D[v]+1;
    dfs(G,v_,v,D);
  }
}

int main(){
  int N;
  cin >> N;
  vector<vector<pair<long long,int>>> G(N);
  for(int i = 0; i < N-1; ++i){
    int u, v, w;
    cin >> u >> v >> w;
    G[u].emplace_back(w,v);
    G[v].emplace_back(w,u);
  }
  vector<int> D(N);
  dfs(G,0,-1,D);
  vector<vector<pair<long long,int>>> V(20,vector<pair<long long,int>>(N));
  for(int i = 0; i < N; ++i){
    for(auto e : G[i]){
      int v_ = e.second;
      if(D[i] == D[v_]+1){
        V[0][i] = e;
      }
    }
  }
  // cerr << "D : ";
  // for(auto d : D) cerr << d << " ";
  // cerr << endl;
  for(int i = 1; i < 20; ++i){
    for(int j = 0; j < N; ++j){
      auto s = V[i-1][j];
      auto t = V[i-1][s.second];
      V[i][j] = {s.first+t.first,t.second};
    }
  }
  auto solve = [&](int u, int v){
                 long long ret = 0;
                 if(D[u] < D[v]) swap(u,v);
                 while(D[u] > D[v]){
                   ret += V[0][u].first;
                   u = V[0][u].second;
                 }
                 if(u == v){
                   return make_pair(ret,v);
                 }
                 for(int k = 19; k >= 0; --k){
                   if(V[k][u].second != V[k][v].second){
                     ret += V[k][u].first + V[k][v].first;
                     u = V[k][u].second;
                     v = V[k][v].second;
                   }
                 }
                 ret += V[0][u].first + V[0][v].first;
                 return make_pair(ret,V[0][u].second);
               };
  int Q;
  cin >> Q;
  while(Q--){
    int k = 3;
    vector<int> X(k);
    for(int i = 0; i < k; ++i) cin >> X[i];
    auto p = solve(X[0],X[1]);
    auto q = solve(X[1],X[2]);
    auto r = solve(X[2],X[0]);
    // cerr << p.first << " " << q.first << " " << r.first << endl;
    long long ans = p.first + q.first + r.first;
    ans /= 2;
    cout << ans << endl;
  }
}
0