#include "bits/stdc++.h" #include #define rep(i,n) for(int i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector> #define vl vector #define vi vector #define vii vector> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits::max(); static const int intMAX = numeric_limits::max(); static const ll llMIN = numeric_limits::min(); static const int intMIN = numeric_limits::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000007; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; template void Printvector(std::vector a){ int size = a.size(); rep(i,size){ cout< void Printvector(std::vector> a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout< prime_factor(int64_t n) { unordered_map ret; for(int64_t i = 2; i * i <= n; i++) { while(n % i == 0) { ret[i]++; n /= i; } } if(n != 1) ret[n] = 1; return ret; } template vector getaccum(vector a){ int size=a.size(); vector ans(size); ans[0]=a[0]; for(int i=0;i accum,int l,int r){//閉区間[l,r]の総和 if(l==0){ return accum[r]; }else{ return accum[r]-accum[l-1]; } } //Segment Tree template class SegmentTree{ public: int n; vector nodes; //constructor SegmentTree(){ ; } SegmentTree(int size,T init){ initialize(size,init); } //関数を定義(minなのかmaxなのかとか) T thisoperator(T a, T b){ return min(a,b); } void update(int x,T a){//xがindex x+=n-1; nodes[x]=a; while(x>0){ x=(x-1)/2; nodes[x]=thisoperator(nodes[2*x+1],nodes[2*x+2]); } } void initialize(int inputn,T init){ int k=0; while(inputn>(1< ((1< 適当に返す //default に注意! if(nowr <= reql || reqr <= nowl) return (T)10000000000; // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う if(reql <= nowl && nowr <= reqr) return nodes[nowindex]; // 要求区間が対象区間の一部を被覆 -> 子について探索を行う // 左側の子を vl ・ 右側の子を vr としている // 新しい対象区間は、現在の対象区間を半分に割ったもの T val1 = sec_get(reql, reqr, 2*nowindex+1, nowl, (nowl+nowr)/2); T val2 = sec_get(reql, reqr, 2*nowindex+2, (nowl+nowr)/2, nowr); return thisoperator(val1, val2); } void Printn(){ cout<<"Printvector Seg"< class LCA{ public: int n;//総ノード数 struct LCA_data{ int index; T depth; }; SegmentTree seg; //DFSでグラフTを根から探索した際の頂点の訪問順を並べた列S=(v0,v1,...,vM−1) vector nodes; vector Firstloc; //constructor LCA(int size){ initialize(size); } void initialize(int inputn){ n = inputn; Firstloc=vector (n,n+100); } void Printn(){ cout<<"Printvector lca index"<r)swap(l,r); return seg.sec_get(l,r); } void EndpreDFS(){ //セグ木を作る n=nodes.size(); seg.initialize(n,(T)100000000); int cnt=0; for(auto i:nodes){ seg.update(cnt,nodes[cnt].depth); cnt++; } } T getdepth(int index){ return nodes[Firstloc[index]].depth; } }; //グラフ LCA lca(0); struct edge{ int to; ll length; int num; int pair; }; struct treev{ int num; vector nexts; }; vector vs; vector es; int cmax=0; void createtreenode(int num){//引数は頂点の数 vs=vector(num); /*treev* newt; try{ treev* newt=new treev; } catch (std::bad_alloc&) { // メモリ確保に失敗 // エラー処理 }*/ rep(i,num){ vs[i].num=i; } return ; } void insertree_bidire(ll len,int Va,int Vb,int num){//結ぶ頂点を //双方向 es.pb({Va,len,num,-1}); es.pb({Vb,len,num,-1}); int size=es.size(); es[size-1].pair=size-2; es[size-2].pair=size-1; vs[Va].nexts.push_back(size-1); vs[Vb].nexts.push_back(size-2); return; } void DFS(int root,ll depth,int pre){ //ここにやりたい処理を書く //cout<>n; vl u(n-1),v(n-1),w(n-1); rep(i,n-1){ cin>>u[i]>>v[i]>>w[i]; } createtreenode(n); rep(i,n-1){ insertree_bidire(w[i],u[i],v[i],i); } lca.initialize(n); DFS(0,0,-1); lca.EndpreDFS(); int q; cin>>q; rep(i,q){ int x,y,z; cin>>x>>y>>z; ll n1=lca.getdepth(x)+lca.getdepth(y)-2*lca.getLCAdepth(x,y); ll n2=lca.getdepth(x)+lca.getdepth(z)-2*lca.getLCAdepth(x,z); ll n3=lca.getdepth(z)+lca.getdepth(y)-2*lca.getLCAdepth(y,z); cout<<(n1+n2+n3)/2<