#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_V = 500000; struct Node { int v; int depth; Node(int v = -1, int depth = -1) { this->v = v; this->depth = depth; } bool operator<(const Node &n) const { return depth < n.depth; } }; class StaticRMQ { public: vector dat; int N; void init(int n) { N = 1; while (N < n) N *= 2; for (int i = 0; i < 2 * N - 1; ++i) { dat.push_back(Node(-1, MAX_V)); } } void update(int k, Node a) { k += N - 1; dat[k] = a; while (k > 0) { k = (k - 1) / 2; dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } } ll find_min(int l, int r) { return query(l, r, 0, 0, N).v; } private: Node query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return Node(-1, MAX_V); if (a <= l && r <= b) { return dat[k]; } else { Node vl = query(a, b, k * 2 + 1, l, (l + r) / 2); Node vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } }; class LCA { public: vector vs; vector depth; vector id; vector > G; StaticRMQ rmq; LCA(int N, int root, vector > _G) { G = _G; int k = 0; vs = vector(2 * N - 1); depth = vector(2 * N - 1); id = vector(N, -1); dfs(root, -1, 0, k); rmq.init(k); for (int i = 0; i < k; ++i) { rmq.update(i, Node(vs[i], depth[i])); } } int find_parent(int u, int v) { return rmq.find_min(min(id[u], id[v]), max(id[u], id[v])); } private: void dfs(int v, int p, int d, int &k) { id[v] = k; vs[k] = v; depth[k++] = d; for (int i = 0; i < G[v].size(); ++i) { if (G[v][i] != p) { dfs(G[v][i], v, d + 1, k); vs[k] = v; depth[k++] = d; } } } }; int main() { int N; cin >> N; int a, b, c; vector> G(N); vector> C(N); for (int i = 1; i <= N - 1; ++i) { cin >> a >> b >> c; --a; --b; G[a].push_back(b); G[b].push_back(a); C[a].push_back(c); C[b].push_back(c); } int root = 0; vector p_cost(N, 0); vector visited(N, false); queue que; queue c_que; que.push(root); c_que.push(0); while (not que.empty()) { int v = que.front(); que.pop(); int cost = c_que.front(); c_que.pop(); if (visited[v]) continue; visited[v] = true; p_cost[v] = cost; for (int i = 0; i < G[v].size(); ++i) { int u = G[v][i]; int c = C[v][i]; que.push(u); c_que.push(cost + c); } } int Q; cin >> Q; LCA lca(N, root, G); int s, t; for (int i = 0; i < Q; ++i) { cin >> s >> t; --s; --t; int p = lca.find_parent(s, t); int c1 = p_cost[s]; int c2 = p_cost[t]; int c3 = p_cost[p]; cout << c1 + c2 - 2 * c3 << endl; } return 0; }