結果

問題 No.898 tri-βutree
ユーザー hjgjkvkhjvvhgbxctgdhjgjkvkhjvvhgbxctgd
提出日時 2021-12-16 19:02:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 485 ms / 4,000 ms
コード長 2,436 bytes
コンパイル時間 2,805 ms
コンパイル使用メモリ 208,916 KB
実行使用メモリ 27,224 KB
最終ジャッジ日時 2023-10-11 17:44:32
合計ジャッジ時間 14,141 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 313 ms
27,224 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 2 ms
4,352 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 2 ms
4,352 KB
testcase_06 AC 2 ms
4,352 KB
testcase_07 AC 480 ms
22,364 KB
testcase_08 AC 485 ms
22,368 KB
testcase_09 AC 478 ms
22,416 KB
testcase_10 AC 483 ms
22,572 KB
testcase_11 AC 485 ms
22,420 KB
testcase_12 AC 484 ms
22,320 KB
testcase_13 AC 475 ms
22,376 KB
testcase_14 AC 483 ms
22,304 KB
testcase_15 AC 471 ms
22,328 KB
testcase_16 AC 481 ms
22,276 KB
testcase_17 AC 477 ms
22,424 KB
testcase_18 AC 474 ms
22,564 KB
testcase_19 AC 478 ms
22,564 KB
testcase_20 AC 481 ms
22,268 KB
testcase_21 AC 476 ms
22,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include <atcoder/all>
using namespace std;
//using namespace boost::multiprecision;
//using namespace atcoder;
#define rep(i,n) for(int i=0;i<(n);++i)
#define lep(i,n) for(long long i=0;i<(n);++i)
#define all(x) (x).begin(),(x).end()
#define equals(a,b) (fabs((a)-(b))<eps)
#define F first
#define S second
using ll=long long;
using pi=pair<int,int>;
using pd=pair<double,double>;
using vi=vector<int>;
using vii=vector<vector<int>>;
using vl=vector<long long>;
using vll=vector<vector<long long>>;
using vpi=vector<pair<int,int>>;
using vs=vector<string>;
using vss=vector<vector<string>>;
using vst=vector<set<int>>;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int inf=1<<30;
const ll infl=1LL<<60;
const double eps=(1e-10);
const int mod=1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


struct LCA {
  typedef ll TT;
  int n, bi;
  vi dep;
  vector<TT> d;
  vii to, co, pa;
  LCA(int n):n(n),dep(n),d(n),to(n),co(n){}
  void add(int a, int b, int c=1) {
    to[a].push_back(b); co[a].push_back(c);
    to[b].push_back(a); co[b].push_back(c);
  }
  void dfs(int v, int ndep=0, TT nd=0, int p=-1) {
    dep[v] = ndep; d[v] = nd; pa[0][v] = p;
    rep(i,(to[v]).size()) {
      int u = to[v][i];
      if (u == p) continue;
      dfs(u,ndep+1,nd+co[v][i],v);
    }
  }
  void init(int root=0) {
    bi = 0;
    while (1<<bi <= n) bi++;
    pa = vii(bi,vi(n,-1));
    dfs(root);
    rep(i,bi-1)rep(j,n) pa[i+1][j] = (pa[i][j]==-1?-1:pa[i][pa[i][j]]);
  }
  int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a,b);
    int x = dep[a]-dep[b];
    for (int i = bi-1; i >= 0; --i){
      if(1<<i <= x) a = pa[i][a], x -= 1<<i;
    }
    if (a == b) return a;
    for (int i = bi-1; i >= 0; --i){
      if (pa[i][a] != pa[i][b]) a = pa[i][a], b = pa[i][b];
    }
    return pa[0][a];
  }
  TT dist(int a, int b){
    int c = lca(a,b);
    return d[a]+d[b]-d[c]*2;
  }
};

int main(){
		int n;
		cin>>n;
		LCA g(n);
		rep(i,n-1){
				int a,b,c;
				cin>>a>>b>>c;
				g.add(a,b,c);
		}
		g.init();
		int k;
		cin>>k;
		rep(i,k){
				int a,b,c;
				cin>>a>>b>>c;
				ll ans=(ll)g.dist(a,b)+(ll)g.dist(b,c)+(ll)g.dist(c,a);
				ans/=2;
				cout<<ans<<endl;
		}





    
    return 0;
}
0