class WeightedLCA: def __init__(self, n, edges, e, ope, root = 0): self.n = n self.e = e self.ope = ope self.logn = (n - 1).bit_length() self.root = root self.depth = [-1] * self.n self.parent = [[-1] * n for _ in range(self.logn)] self.weight = [[-1] * n for _ in range(self.logn)] self.dfs(edges) self.doubling() def dfs(self, edges): stack = [self.root] self.depth[self.root] = 0 while stack: pos = stack.pop() for npos, w in edges[pos]: if self.depth[npos] != -1: continue self.depth[npos] = self.depth[pos] + 1 self.parent[0][npos] = pos self.weight[0][npos] = w stack.append(npos) def doubling(self): for i in range(1, self.logn): for j in range(n): if self.parent[i - 1][j] != -1: p = self.parent[i - 1][j] self.parent[i][j] = self.parent[i - 1][p] self.weight[i][j] = self.ope(self.weight[i - 1][j], self.weight[i - 1][p]) def get(self, u, v): if self.depth[v] < self.depth[u]: u, v = v, u du = self.depth[u] dv = self.depth[v] ret = self.e for i in range(self.logn): if (dv - du) >> i & 1: ret = self.ope(ret, self.weight[i][v]) v = self.parent[i][v] if u == v: return ret, u for i in range(self.logn - 1, -1, -1): pu = self.parent[i][u] pv = self.parent[i][v] if pu != pv: ret = self.ope(ret, self.weight[i][u]) ret = self.ope(ret, self.weight[i][v]) u, v = pu, pv ret = self.ope(ret, self.weight[0][u]) ret = self.ope(ret, self.weight[0][v]) u = self.parent[0][u] return ret, u n = int(input()) edges = [[] for _ in range(n)] for _ in range(n - 1): a, b, c = map(int, input().split()) a -= 1 b -= 1 edges[a].append((b, c)) edges[b].append((a, c)) lca = WeightedLCA(n, edges, 0, lambda x, y: x + y) Q = int(input()) for _ in range(Q): u, v = map(int, input().split()) print(lca.get(u - 1, v - 1)[0])