#include #include #include #include #include #include #include using namespace std; #define REP(i,n) for (int i=0;i<(n);++i) #define rep(i,a,b) for(int i=a;i<(b);++i) using ll = long long; constexpr ll INF = 1LL << 60; constexpr int MOD = 998244353; struct Edge { int src, dst, cost; Edge(int s, int d, int c = 1) : src(s), dst(d), cost(c) {} bool operator<(const Edge &e){ return cost < e.cost;} }; using Edges = vector; using Graph = vector; // build O(NlogN), query O(logN) template struct LCA { vector cost; vector depth; vector> par; Graph g; int logn; LCA(int n, Graph g) : cost(n), depth(n), g(g) { logn = 0; while((1<(logn, n)); dfs(0, -1, 0, 0); for(int i = 0; i < logn-1; ++i) { for(int v = 0; v < n; ++v) { par[v][i+1] = par[par[v][i]][i]; } } } void dfs(int v, int p, int d, T c) { if(p != -1) par[v][0] = p; depth[v] = d; cost[v] = c; for(Edge e : g[v]) { if(e.dst == p) continue; dfs(e.dst, v, d+1, cost[v] + e.cost); } } int get_lca(int x, int y) { if(depth[x] > depth[y]) swap(x, y); for(int i = logn-1; i >= 0; --i) { if(((depth[y] - depth[x])>>i) & 1) y = par[y][i]; } if(x == y) return y; for(int i = logn-1; i >= 0; --i) { int nx = par[x][i], ny = par[y][i]; if(nx != ny) x = nx, y = ny; } return par[y][0]; } T get_length(int x, int y) { int z = get_lca(x, y); return cost[x] + cost[y] - cost[z] * 2; } }; ll q, n, k, u, v, w; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> n; Graph g(n); REP(i, n-1) { cin >> u >> v >> w; g[u].emplace_back(u, v, w); g[v].emplace_back(v, u, w); } LCA lca(n, g); cin >> q; REP(i, q) { cin >> u >> v >> w; int dep = -1, v1, v2, v3, a; a = lca.get_lca(u, v); if(lca.depth[a] > dep) v1 = u, v2 = v, v3 = w, dep = lca.depth[a]; a = lca.get_lca(v, w); if(lca.depth[a] > dep) v1 = v, v2 = w, v3 = u, dep = lca.depth[a]; a = lca.get_lca(w, u); if(lca.depth[a] > dep) v1 = w, v2 = u, v3 = v, dep = lca.depth[a]; cout << lca.get_length(v1, v2) + lca.get_length(lca.get_lca(v1, v2), v3) << '\n'; } return 0; }