#include using namespace std; using ll = long long; using VI = vector; using VV = vector; using VS = vector; // tourist set template string to_string(pair p); template string to_string(tuple p); template string to_string(tuple p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template string to_string(bitset v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast('0' + v[i]); } return res; } template string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif // tourist set end templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b(const Node &another) const { return distance > another.distance; } }; struct Dijkstra{ vector d; vector > graph; vector done; // ノード数を入れる void initialize(ll size){ d.resize(size); done.resize(size); graph.resize(size); reset(); } void reset(){ ll N = graph.size(); FOR(i, 0, N){ d[i] = inf; done[i] = false; } } ll distance(int i){ if(d.size()<=i) return -1; return d[i]; } void print_graph(){ FOR(i, 0, graph.size()){ cout << i << " -> "; for(auto edge : graph[i]){ cout << edge.to << " "; } cout << endl; } p("distance"); FOR(i, 0, graph.size()){ ll d = distance(i); cout << i << " " << d << endl; } } void register_edge(ll a, ll b, ll cost){ auto edge = Edge(b, cost); graph[a].push_back(edge); } void calc_shortest_path(ll from=0){ priority_queue, greater > que; auto node = Node(); // 始点 node.index = from; node.distance = 0; que.push(node); while(!que.empty()){ // 1番distanceが小さいノード Node n = que.top(); que.pop(); if(done[n.index]){ continue; } done[n.index] = true; d[n.index] = n.distance; auto edge_list = graph[n.index]; for(auto edge : edge_list){ // 短くなるノードがあれば if(!done[edge.to] && n.distance + edge.cost < d[edge.to]){ ll shorter_distance = n.distance + edge.cost; que.push(Node(shorter_distance, edge.to)); } } } } }; void vprint(vector A){ ll L = A.size(); FOR(i, 0, L){ if(i) cout << ' '; cout << A[i]; } cout << endl; } // LCA set VV G; const int N_MAX = 100010; const int MAX_LOG_V = 20; ll depth[N_MAX] = {}; ll parent[MAX_LOG_V][N_MAX] = {}; void dfs(ll index, ll prev, ll _depth){ depth[index] = _depth; parent[0][index] = prev; auto list = G[index]; for(ll to : list){ if(to==prev){ continue; } dfs(to, index, _depth+1); } return; } ll LCA(ll a, ll b){ if(a==b){ return a; } // aよりbが深い(または同じ)と仮定する if(depth[a] > depth[b]){ swap(a, b); } // bを根側に辿っていく ll diff_depth = depth[b] - depth[a]; FOR(k, 0, MAX_LOG_V){ if(diff_depth >> k & 1){ b = parent[k][b]; } } // aとbの深さが揃った if(a==b){ return a; } // 大きい歩幅で共通親までジャンプ for(int k=MAX_LOG_V-1; k>=0; k--){ if(parent[k][a] != parent[k][b]){ a = parent[k][a]; b = parent[k][b]; } } // 1つ上がLCA return parent[0][a]; } void prepare_LCA(ll N){ // dfs(1, -1, 0); dfs(0, -1, 0); // ダブリングで親 2^k FOR(k, 1, MAX_LOG_V){ FOR(i, 1, N+1){ ll p = parent[k-1][i]; if(p==-1) continue; parent[k][i] = parent[k-1][p]; } } } // LCA set end Dijkstra dij; ll f(ll u, ll v){ ll p = LCA(u, v); ll d = dij.distance(u) + dij.distance(v) - 2*dij.distance(p); return d; } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin >> N; G.resize(N); dij.initialize(N); rep(i, N-1){ ll u, v, w; cin >> u >> v >> w; dij.register_edge(u, v, w); dij.register_edge(v, u, w); G[u].push_back(v); G[v].push_back(u); } dij.calc_shortest_path(0); prepare_LCA(N); ll Q; cin >> Q; while(Q--){ ll x, y, z; cin >> x >> y >> z; ll ans = f(x, y) + f(y, z) + f(z, x); p(ans/2); } return 0; }