#include using namespace std; template < typename Element = long > class SparseTable{ public: function operation; vector> table; vector cf; SparseTable(vector& v, Element e, function operation) : operation(operation){ long isiz = v.size(); long jsiz = 0; while((1 << jsiz) <= isiz) jsiz++; table.resize(isiz, vector(jsiz, e)); for(long i = 0; i < isiz; i++)table[i][0] = v[i]; for(long j = 1; j < jsiz; j++){ for(long i = 0; i + (1 << (j - 1)) < isiz; i++){ table[i][j] = operation(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]); } } cf.resize(isiz + 1); for(long i = 2; i <= isiz; i++) cf[i] = cf[i >> 1] + 1; } Element query(long l, long r/*半開区間*/){ assert(l < r); long b = cf[r - l]; return operation(table[l][b], table[r - (1 << b)][b]); } }; class LowestCommonAncestor{ private: long N; vector visited; vector > Tree; vector > STtable; vector STcf; void make_EularTour(long vis){ EularTour.push_back(depth[vis] * N + vis); visited[vis] = true; for(auto e : Tree[vis]){ if(visited[e]) continue; depth[e] = depth[vis] + 1; make_EularTour(e); EularTour.push_back(depth[vis] * N + vis); } } void make_SparseTable(){ SparseTable st(EularTour, LONG_MAX, [](long a, long b){return min(a, b);}); STtable = st.table; STcf = st.cf; } void make_first(){ long index = 0; for(auto e : EularTour){ first_index[e % N] = min(first_index[e % N], index); index++; } } public: vector depth; vector EularTour; vector first_index; LowestCommonAncestor(vector>& tree, long root) : Tree(tree){ N = Tree.size(); visited.resize(N, false); depth.resize(N, 0); first_index.resize(N, INT_MAX); make_EularTour(root); make_SparseTable(); make_first(); } long query(long l, long r){ long ltmp = l, rtmp = r; l = min(first_index[ltmp], first_index[rtmp]); r = max(first_index[ltmp], first_index[rtmp]) + 1; long b = STcf[r - l]; return min(STtable[l][b], STtable[r - (1 << b)][b]) % N; } }; int main(){ long N; cin >> N; vector> tree(N); vector>> tree_weight(N); for(long i = 0; i < N - 1; i++){ long u, v, w; cin >> u >> v >> w; tree[u].push_back(v); tree[v].push_back(u); tree_weight[u].push_back({v, w}); tree_weight[v].push_back({u, w}); } vector dist(N, 0); vector bfs_vis(N, false); bfs_vis[0] = true; stack> bfs; bfs.push({0, 0}); while(not bfs.empty()){ auto [e, w] = bfs.top(); bfs.pop(); for(auto [e2, w2] : tree_weight[e]){ if(bfs_vis[e2]) continue; bfs_vis[e2] = true; dist[e2] = w + w2; bfs.push({e2, w + w2}); } } LowestCommonAncestor lca(tree, 0); long Q; cin >> Q; while(Q--){ long x, y, z; cin >> x >> y >> z; long dxy = dist[x] + dist[y] - 2 * dist[lca.query(x, y)]; long dyz = dist[y] + dist[z] - 2 * dist[lca.query(y, z)]; long dzx = dist[z] + dist[x] - 2 * dist[lca.query(z, x)]; cout << (dxy + dyz + dzx) / 2 << '\n'; } }