結果

問題 No.898 tri-βutree
ユーザー hjgjkvkhjvvhgbxctgd
提出日時 2021-12-16 19:02:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 467 ms / 4,000 ms
コード長 2,436 bytes
コンパイル時間 2,660 ms
コンパイル使用メモリ 203,932 KB
最終ジャッジ日時 2025-01-26 23:36:24
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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