#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) #define INF 2e9 #define MOD 1000000007 //#define MOD 998244353 #define LINF (long long)4e18 #define jck 3.141592 using ll = long long; using Pi = pair; using Pl = pair; vector> G; void dijkstra(int p,vector &dist,vector visited){ priority_queue> q; dist[p] = 0; q.push(make_pair(0,p)); while(!q.empty()){ pair f = q.top(); q.pop(); int u = f.second; if(dist[u] < f.first*(-1)) continue; visited[u] = true; rep(i,G[u].size()){ int v = G[u][i].first; if(visited[v] == true) continue; if(dist[v] > dist[u] + G[u][i].second){ dist[v] = dist[u] + G[u][i].second; q.push(make_pair(dist[v]*(-1),v)); } } } } template class LCA{ public: const int n = 0; const int log2_n = 0; vector> par; vector depth; LCA(){} LCA(const T &g,int root) : n(g.size()),log2_n(log2(n)+1),par(log2_n,vector(n)),depth(n){ dfs(g,root,-1,0); rep(k,log2_n-1)rep(v,g.size()){ if(par[k][v] < 0) par[k+1][v] = -1; else par[k+1][v] = par[k][par[k][v]]; } } void dfs(const T &g,int v,int p,int d){ par[0][v] = p; depth[v] = d; for(auto &e : g[v]){ if(e.first != p) dfs(g,e.first,v,d+1); } } int get(int u,int v){ if(depth[u] > depth[v]) swap(u,v); rep(k,log2_n){ if((depth[v]-depth[u]) >> k&1){ v = par[k][v]; } } if(u == v) return u; for(int k = log2_n-1; k >= 0; k--){ if(par[k][u] != par[k][v]){ u = par[k][u]; v = par[k][v]; } } return par[0][u]; } }; int main(){ int N; cin >> N; G.resize(N); rep(i,N-1){ int u,v,w; cin >> u >> v >> w; G[u].emplace_back(v,w); G[v].emplace_back(u,w); } vector dist(N,LINF); vector visited(N,false); dijkstra(0,dist,visited); LCA>> l(G,0); int Q; cin >> Q; while(Q--){ int x,y,z; cin >> x >> y >> z; int d1 = l.get(x,y); int d2 = l.get(y,z); int d3 = l.get(z,x); ll ans = 0; ans += dist[x]+dist[y]-dist[d1]*2; ans += dist[y]+dist[z]-dist[d2]*2; ans += dist[z]+dist[x]-dist[d3]*2; ans /= 2; cout << ans << endl; } }