#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, ll> P; template< typename G=vector<vector<int>> > struct HeavyLightDecomposition { G &g; vector< int > sz, in, out, head, rev, par; HeavyLightDecomposition(G &g) : g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {} void dfs_sz(int idx, int p) { par[idx] = p; sz[idx] = 1; if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back()); for(auto &to : g[idx]) { if(to == p) continue; dfs_sz(to, idx); sz[idx] += sz[to]; if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to); } } void dfs_hld(int idx, int par, int ×) { in[idx] = times++; rev[in[idx]] = idx; for(auto &to : g[idx]) { if(to == par) continue; head[to] = (g[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } void build() { dfs_sz(0, -1); int t = 0; dfs_hld(0, -1, t); } int la(int v, int k) { while(1) { int u = head[v]; if(in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) return u; } } template< typename T, typename Q, typename F > T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) { T l = ti, r = ti; for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v), swap(l, r); if(head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return f(f(q(in[u] + edge, in[v] + 1), l), r); } template< typename Q > void add(int u, int v, const Q &q, bool edge = false) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } }; vector<vector<int>> G; vector<vector<P>> g; ll d[100010]; void dfs(int x, int p){ for(auto q:g[x]){ int y=q.first; ll w=q.second; if(y!=p){ d[y]=d[x]+w; dfs(y, x); } } } int main() { int n; cin>>n; g.resize(n); G.resize(n); for(int i=0; i<n-1; i++){ int u, v; ll w; cin>>u>>v>>w; G[u].push_back(v); G[v].push_back(u); g[u].push_back({v, w}); g[v].push_back({u, w}); } HeavyLightDecomposition<> hld(G); hld.build(); dfs(0, -1); int Q; cin>>Q; for(int i=0; i<Q; i++){ int x, y, z; cin>>x>>y>>z; ll ans=0; int p=hld.lca(x, y); ans+=d[x]+d[y]-2*d[p]; p=hld.lca(y, z); ans+=d[y]+d[z]-2*d[p]; p=hld.lca(z, x); ans+=d[z]+d[x]-2*d[p]; ans/=2; cout<<ans<<endl; } return 0; }