//sub-BOF //#define _AOJ_ /*vvv> zzzzzI .---. zzuzuI .vgggg&,. +++++= dAC:|I .WbbWo JMM9^```?TMB` ..&gNNg,. gggggggJ, qgggggggg] (&&&&&&&&[ c+OA&J, (&&&&&&+J, .cJeAA&-. (&&&&&&&&x .&AA&=-. +++++= dTqk|I Xpbpbp JM#` (M#^ ?MMp MM| +TMN. JMF ' |yk ` dVY 7Vk, Vy XV cVf ?Y! JM V$ ` +++++= dcf:|I Xppppp dMN .MM+ .MM MM| MM] JMMMMMM+ |@tqkoh) ,y0 (V$ yyyyyyyV7 VV JMWyZWr TWVVVVW&, ++++++ d7qk|0 Xppppp ^HMN, _.db WMm, .MMF MM| ..MM` JMF . |yk .WV&. .XW' yy 4yn. jyn +. JM #S `++++` ?ZZZX= ?WWWW= -THMMMMH9^ (TMMMMM9! MMMMMMM"" JMMMMMMMME |UU. ?TUUUUY= UU. (UU- ^7TUUUV7! JUUUUUUUU 7TUNKO*/ #pragma region template #pragma region basic #pragma GCC optimize ("O3")//#pragma GCC optimize ("fast-math") #pragma GCC target ("avx2") #include "bits/stdc++.h" using namespace std; typedef long long lint; typedef long double ld; typedef string cs; #pragma endregion #pragma region rep #define _vcppunko4(tuple) _getname4 tuple #define _getname4(_1,_2,_3,_4,name,...) name #define _getname3(_1,_2,_3,name,...) name #define _trep2(tuple) _rep2 tuple #define _trep3(tuple) _rep3 tuple #define _trep4(tuple) _rep4 tuple #define _rep1(n) for(lint i=0;i=0;--i) #define _rrep2(i,n) for(lint i=n-1;i>=0;--i) #define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i) #define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c) #define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__)) #define per(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_rrep1))((__VA_ARGS__)) #define each(c) for(auto &e:c) #pragma endregion #pragma region io template istream& operator>>(istream& is,vector& vec); template istream& operator>>(istream& is,array& vec); template istream& operator>>(istream& is,pair& p); template ostream& operator<<(ostream& os,vector& vec); template ostream& operator<<(ostream& os,pair& p); template istream& operator>>(istream& is,vector& vec){ for(T& x: vec) is>>x;return is; } template istream& operator>>(istream& is,pair& p){ is>>p.first;is>>p.second;return is; } template ostream& operator<<(ostream& os,pair& p){ os< ostream& operator<<(ostream& os,vector& vec){ os< ostream& operator<<(ostream& os,deque& deq){ os< HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); inline void in(){ SetConsoleTextAttribute(hConsole,10); } template inline void in(Head&& head,Tail&&... tail){ SetConsoleTextAttribute(hConsole,15); cin>>head;in(move(tail)...); } #else inline void in(){} template inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); } #endif inline bool out(){ return(cout<<'\n',0); } template inline bool out(T t){ return(cout< inline bool out(Head head,Tail... tail){ cout< inline void alloc(T &c,lint s){ rep(c.size())c[i].resize(s); } #define alc alloc #pragma endregion #pragma region TA #define lin(...) lint __VA_ARGS__;in(__VA_ARGS__) #define stin(...) string __VA_ARGS__;in(__VA_ARGS__) #define vin(type,name,size) vector name(size);in(name) #define vvin(type,name,h,...) vector>name(h,vector(__VA_ARGS__));in(name) #define all(v) v.begin(),v.end() #define pb push_back #define fi e.first #define se e.second #define YES(c) cout<<((c)?"YES\n":"NO\n"),0 #define Yes(c) cout<<((c)?"Yes\n":"No\n"),0 #define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0 #define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0 #define o(p) cout<r)swap(l,r); inline constexpr lint gcd(lint a,lint b){ if(!a||!b)return 0;while(b){ lint c=b;b=a%b;a=c; }return a; } template inline constexpr bool chmin(T &mn,const T &cnt){ if(mn>cnt){ mn=cnt;return 1; } else return 0; } template inline constexpr bool chmax(T &mx,const T &cnt){ if(mx #define fn(ty1,ty2,ex) [](ty1 a,ty2 b){ return(ex); } #define lfn(ex) [](lint a,lint b){ return(ex); } #pragma endregion #pragma region other #ifdef __ENV_TQK__ #define deb(...) out(__VA_ARGS__) #define dsp(ex) sp(ex) #define dno(ex) no(ex) #else #define deb(...) 0 #define dsp(ex) 0 #define dno(ex) 0 #endif struct Fastio{ Fastio(){ cin.tie(0),cout.tie(0); ios::sync_with_stdio(0); cout< md_tmp class mint{ using u64=uint_fast64_t; public: u64 a; constexpr mint(const u64 x=0) noexcept: a(x%md){} constexpr u64 &value() noexcept{ return a; } constexpr const u64 &value() const noexcept{ return a; } constexpr mint operator+(const mint rhs) const noexcept{ return mint(*this)+=rhs; } constexpr mint operator-(const mint rhs) const noexcept{ return mint(*this)-=rhs; } constexpr mint operator*(const mint rhs) const noexcept{ return mint(*this)*=rhs; } constexpr mint operator^(const lint rhs) const noexcept{ return mint(*this)^=rhs; } constexpr mint operator/(const mint rhs) const noexcept{ return mint(*this)/=rhs; } constexpr mint &operator+=(const mint rhs) noexcept{ a+=rhs.a; if(a>=md)a-=md; return *this; } constexpr mint &operator-=(const mint rhs) noexcept{ if(aa; while(exp){ if(exp&1)*this*=base; base*=base; exp>>=1; } return *this; } constexpr mint &operator/=(const mint rhs) noexcept{ a=(*this*(rhs^(md-2))).a; return *this; } }; md_tmp istream& operator>>(istream& os,mint& m){ os>>m.a,m.a%=md; return os; } md_tmp ostream& operator<<(ostream& os,const mint& m){ return os< ncr(lint n,lint r){ if(n(0); mintncr_res=1,ncr_div=1; rep(r)ncr_res*=(n-i),ncr_div*=(r-i); return ncr_res/ncr_div; } #ifndef _AOJ_ mint<> operator""m(const unsigned long long n){ return mint<>(n); } mint<998244353> operator""m9(const unsigned long long n){ return mint<998244353>(n); } mint<1000003> operator""m3(const unsigned long long n){ return mint<1000003>(n); } #endif #pragma endregion #pragma region P class P{ public:lint f,s; P(lint a,lint b):f(a),s(b){}; P():f(0),s(0){}; }; istream& operator>>(istream& os,P& p){ os>>p.f>>p.s;return os; } constexpr bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); } constexpr bool operator<=(const P& l,const P& r){ return!(l.f-r.f?l.f>r.f:l.s>r.s); } constexpr bool operator>=(const P& l,const P& r){ return!(l.f-r.f?l.f>(istream& os,edge& e){ os>>e.src>>e.to>>e.cost;return os; } using Matrix=vector >; using Edges=vector; using Weighted=vector; using UnWeighted=vector >; // HLD( , root ) // === .build() === // .fold(hi, lo, func, inclusive) // where func(l, r) proceeds with [l, r) // === O(1) === // .in(a) : in-time of Euler Tour : alias = .[a] // .out(a) : out-time of Euler Tour // .rev(a) : rev[in[a]] = a // .head(a) : ascend all light edges // .tail(a) : descend all heavy edges // --- // .subtree_size(a) // .depth(a) : 0-indexed // .parent(a) : -1 if [a] is root // .heavy(a) : [a] cannot be a leaf. return the node opposite of the heavy edge // === O(log n) === // .climb(a) // .descendTo(from, to, steps) // .steps(a, b) // === --- === // for subtree : [ .in(a) , .out(a) ) // (exclusive) : [ .in_exclusive(a) , .out(a) ) // HL-Decomposition {{{ // based on Euler Tour struct HLD{ public: using size_type = std::size_t; using graph_type = std::vector< std::vector< int > >; private: size_type n; std::vector< size_type > hd,tl; std::vector< size_type > sub; std::vector< size_type > dep; std::vector< int > par; std::vector< size_type > vid; size_type root; graph_type tree; public: HLD(): n(0){} HLD(size_type n,size_type root = 0) : n(n),hd(n),tl(n),sub(n),dep(n),par(n),vid(n),tree(n){ setRoot(root); } HLD(const graph_type &tree,size_type root): HLD(tree.size(),root){ this->tree = tree; } void setRoot(size_type root){ assert(root < n); this->root = root; } private: bool built = 0; std::vector< size_type > vid_rev; public: void build(){ assert(!built && n); built = 1; vid_rev.resize(n); hd[root] = root; dfs0(); dfs1(); for(size_type i = 0; i < n; i++) vid_rev[vid[i]] = i; } private: void dfs0(){ std::vector< int > used(n); std::vector< std::tuple< size_type,int,size_type > > stk; stk.reserve(n); stk.emplace_back(root,-1,0); while(stk.size()){ size_type i,d; int p; std::tie(i,p,d) = stk.back(); if(!used[i]){ used[i] = 1; par[i] = p; dep[i] = d; for(auto &j : tree[i]) if(j != p){ stk.emplace_back(j,i,d + 1); } } else{ stk.pop_back(); sub[i] = 1; for(auto &j : tree[i]) if(j != p){ if(sub[j] > sub[tree[i].back()]){ std::swap(tree[i].back(),j); } sub[i] += sub[j]; } if(tree[i].back() != p){ tl[i] = tl[tree[i].back()]; } else{ tl[i] = i; } } } } void dfs1(){ std::vector< int > used(n); std::vector< std::tuple< size_type,int > > stk; stk.reserve(n); stk.emplace_back(root,-1); size_type id = 0; while(stk.size()){ size_type i; int p; std::tie(i,p) = stk.back(),stk.pop_back(); vid[i] = id++; for(auto j : tree[i]) if(j != p){ hd[j] = j == tree[i].back() ? hd[i] : j; stk.emplace_back(j,i); } } } public: size_type operator[](size_type i) const{ return in(i); } size_type in(size_type i) const{ assert(built); assert(i < n); return vid[i]; } size_type in_exclusive(size_type i) const{ return in(i) + 1; } size_type out(size_type i) const{ assert(built); assert(i < n); return vid[i] + sub[i]; } size_type out_exclusive(size_type i) const{ return out(i) - 1; } size_type head(size_type i) const{ assert(built); return hd.at(i); } size_type tail(size_type i) const{ assert(built); return tl.at(i); } size_type rev(size_type i) const{ assert(built); return vid_rev.at(i); } size_type subtree_size(size_type i) const{ assert(built); return sub.at(i); } size_type depth(size_type i) const{ assert(built); return dep.at(i); } int parent(size_type i) const{ assert(built); return par.at(i); } size_type steps(size_type a,size_type b) const{ assert(built); assert(a < n && b < n); return dep[a] + dep[b] - 2 * dep[lca(a,b)]; } size_type climb(size_type a,long long t) const{ assert(built); assert(a < n && t >= 0); while(t){ long long c = std::min< long long >(vid[a] - vid[hd[a]],t); t -= c; a = vid_rev[vid[a] - c]; if(t && a != root){ t--; a = par[a]; } if(a == root) break; } return a; } size_type descendTo(size_type from,size_type to,long long steps) const{ assert(built); assert(steps >= 0); assert(from < n && to < n); return climb(to,dep[to] - dep[from] - steps); } void add_edge(size_type a,size_type b){ assert(built); assert(a < n && b < n); tree[a].emplace_back(b); tree[b].emplace_back(a); } size_type lca(size_type a,size_type b) const{ assert(built); assert(a < n && b < n); while(1){ if(vid[a] > vid[b]) std::swap(a,b); if(hd[a] == hd[b]) return a; b = par[hd[b]]; } } size_type heavy(size_type a) const{ assert(built); assert(a < n); assert(tree[a].back() != par[a]); return tree[a].back(); } void _fold_vertex(size_type hi,int lo,std::function< void(int,int) > f, bool inclusive) const{ assert(built); assert(hi < n && 0 <= lo && lo < (int)n); while(lo != -1 && dep[lo] >= dep[hi]){ size_type nex = max(vid[hd[lo]],vid[hi]); f(nex + (nex == vid[hi] && !inclusive),vid[lo] + 1); lo = par[hd[lo]]; } } void _fold_edge(size_type hi,int lo,std::function< void(int,int) > f) const{ assert(built); assert(hi < n && 0 <= lo && lo < (int)n); while(lo != -1 && dep[lo] >= dep[hi]){ size_type nex = max(vid[hd[lo]],vid[hi]); f(nex+(nex==vid[hi]),vid[lo]+1); lo = par[hd[lo]]; } } void fold_path_vertex(int s,int t,std::function< void(int,int) > f) const{ int l=lca(s,t); _fold_vertex(l,s,f,1); _fold_vertex(l,t,f,0); } void fold_path_edge(int s,int t,std::function< void(int,int) > f) const{ int l=lca(s,t); _fold_edge(l,s,f); _fold_edge(l,t,f); } void fold_subtree_vertex(int i,std::function< void(int,int) > f) const{ f(in(i),out(i)); } void fold_subtree_edge(int i,std::function< void(int,int) > f) const{ f(in(i)+1,out(i)); } size_type distance(size_type a,size_type b) const{ return depth(a)+depth(b)-2*depth(lca(a,b)); } size_type size() const{ return n; } }; // }}} class Ushi{ public: using T=lint; using func=function; int n,sz; vector node; func f; T e; Ushi(vector v,func f,T e):f(f),e(e){ sz=v.size();n=1; while(n0;--i)node[i]=f(node[2*i],node[2*i+1]); } T* at(int i){ return &node[i+n]; }//use like *tree.at(i)=x,tree.adjust(i); void adjust(int i){ i+=n;while(i>>=1)node[i]=f(node[2*i],node[2*i+1]); } T fold(int a,int b,int k=1,int l=0,int r=-1){ if(r<0)r=n; if(r<=a||b<=l)return e; if(a<=l&&r<=b)return node[k]; return f(fold(a,b,2*k,l,(l+r)/2),fold(a,b,2*k+1,(l+r)/2,r)); } };//verified(DSL_2_A,DSL_2_B):http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3604788#1 int main(){ lint n,u,v,w;in(n); UnWeighted g(n); map _len; vectorlen(n);//after hld rep(n-1){ in(u,v,w); psort(u,v); g[u].pb(v),g[v].pb(u); _len[P(u,v)]=w; } HLD h(g,0);h.build(); rep(i,1,n){ int u=h.parent(i),v=i; psort(u,v); len[h.in(i)]=_len[P(u,v)]; } Ushi ki(len,[](lint a,lint b){return a+b;},0); //end-input lint q;in(q); while(q--){ lint x,y,z,ans=0;in(x,y,z); { lint d1=h.depth(h.lca(x,y)),d2=h.depth(h.lca(y,z)),d3=h.depth(h.lca(z,x)); if(d2>d1&&d2>d3)swap(x,z); else if(d3>d1&&d3>d2)swap(y,z); } h.fold_path_edge(x,y, [&](int l,int r){ans+=ki.fold(l,r);}); h.fold_path_edge(z,h.lca(x,y),[&](int l,int r){ans+=ki.fold(l,r);}); out(ans); } } //sub-EOF