#include using namespace std; using ll = long long; using VI = vector; using VV = vector; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define rep(i,b) FOR(i, 0, b) #define ALL(v) (v).begin(), (v).end() #define p(s) cout<<(s)<(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; for(auto edge : graph[n.index]){ // 短くなるノードがあれば 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)); } } } } }; // 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; for(ll to : G[index]){ 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(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; // editorial参照 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; }