結果

問題 No.898 tri-βutree
ユーザー _____TAB__________TAB_____
提出日時 2019-10-04 22:18:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,102 bytes
コンパイル時間 933 ms
コンパイル使用メモリ 86,760 KB
実行使用メモリ 61,952 KB
最終ジャッジ日時 2024-10-03 07:55:59
合計ジャッジ時間 12,045 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
                 }
                 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]);
    auto s = solve(q.second,X[0]);
    // cerr << p.first << " " << r.first << " " << s.first << endl;
    long long ans = p.first + r.first - s.first;
    cout << ans << endl;
  }
}
0