#include #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; typedef long long ll; struct LCA { vector> parent; // parent[d][v] := 2^d-th parent of v vector depth; LCA() { } LCA(const vector> &G, int r = 0){ init(G, r); } void init(const vector> &G, int r = 0) { int V = (int)G.size(); int h = 1; while((1 << h) < V) ++h; parent.assign(h, vector (V, -1)); depth.assign(V, -1); dfs(G, r, -1, 0); for(int i = 0; i + 1 < (int)parent.size(); ++i){ for(int v = 0; v < V; ++v) { if(parent[i][v] != -1){ parent[i + 1][v] = parent[i][parent[i][v]]; } } } } void dfs(const vector> &G, int v, int p, int d) { parent[0][v] = p; depth[v] = d; for(auto e : G[v]) if(e != p) dfs(G, e, v, d + 1); } int query(int u, int v) { if(depth[u] > depth[v]) swap(u, v); for(int i = 0; i < (int)parent.size(); ++i) { if((depth[v] - depth[u]) & (1 << i)) v = parent[i][v]; } if(u == v) return u; for(int i = (int)parent.size() - 1; i >= 0; --i) { if(parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } return parent[0][u]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[query(u, v)]; } bool is_on_path(int u, int v, int x) { return dist(u, x) + dist(x, v) == dist(u, v); } }; int main(){ cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; vector>> G(N); vector> H(N); rep(i,N-1) { int u,v,w; cin >> u >> v >> w; G[u].push_back({v, w}); G[v].push_back({u, w}); H[u].push_back(v); H[v].push_back(u); } int ROOT = 0; vector sum(N, 0); function dfs = [&](int v, int p) -> void { for(auto [to, w] : G[v]) { if(to != p) { sum[to] = sum[v] + w; dfs(to, v); } } }; dfs(ROOT, -1); LCA lca(H, ROOT); int Q; cin >> Q; rep(_,Q) { int x,y,z; cin >> x >> y >> z; ll ans = 0; ans += sum[x] + sum[y] - 2 * sum[lca.query(x, y)]; ans += sum[y] + sum[z] - 2 * sum[lca.query(y, z)]; ans += sum[z] + sum[x] - 2 * sum[lca.query(z, x)]; ans /= 2; cout << ans << "\n"; } }