class HeavyLightDecomposition: # HL 分解 (HLD) def __init__(self, E, root=1): # E は双方向に辺を張った木で、破壊的に有向グラフに変更される # O(N) self.E = E self.root = root self.N = N = len(E) # 頂点数 self.Parent = [-1] * N # 頂点番号 v -> 親ノード self.Size = [-1] * N # 頂点番号 v -> 部分木のサイズ self.dfs1() self.Mapping = [-1] * N # 頂点番号 v -> 内部インデックス self.Head = list(range(N)) # 頂点番号 v -> v を含む heavy path の左端の頂点番号 self.Depth = [0] * N # 頂点番号 v -> 深さ(root から v までの距離) self.dfs2() def dfs1(self): E = self.E Parent, Size = self.Parent, self.Size Path = [self.root] Idx_edge = [0] while Path: v = Path[-1] idx_edge = Idx_edge[-1] Ev = E[v] if idx_edge != len(Ev): # 行きがけ・通りがけ 辺の数だけ実行される u = Ev[idx_edge] Idx_edge[-1] += 1 E[u].remove(v) # 有向グラフならここをコメントアウトする Parent[u] = v Path.append(u) Idx_edge.append(0) else: # 帰りがけ 頂点の数だけ実行される if len(Ev) >= 2: ma = -1 argmax = None for i, u in enumerate(Ev): if Size[u] > ma: ma = Size[u] argmax = i Ev[0], Ev[argmax] = Ev[argmax], Ev[0] Size[v] = sum(Size[u] for u in Ev) + 1 Path.pop() Idx_edge.pop() def dfs2(self): E = self.E Mapping = self.Mapping Head = self.Head Depth = self.Depth k = 0 St = [self.root] while St: v = St.pop() Mapping[v] = k k += 1 Ev = E[v] if Ev: Head[Ev[0]] = Head[v] St += Ev[::-1] for u in Ev: Depth[u] = Depth[v] + 1 # distance を使わないのならここをコメントアウトする def lca(self, v, u): # O(logN) Parent = self.Parent Mapping = self.Mapping Head = self.Head while True: if Mapping[v] > Mapping[u]: v, u = u, v # v の方を根に近くする if Head[v] == Head[u]: return v u = Parent[Head[u]] def distance(self, v, u): # O(logN) Depth = self.Depth return Depth[v] + Depth[u] - 2 * Depth[self.lca(v, u)] from collections import deque n = int(input()) E = [[] for _ in range(n + 1)] EC = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b, c = map(int, input().split()) E[a].append(b) EC[a].append((b, c)) E[b].append(a) EC[b].append((a, c)) INF = 10**18 C = [INF for _ in range(n + 1)] C[1] = 0 Que = deque([1]) while Que: cp = Que.popleft() cc = C[cp] for np, dc in EC[cp]: if cc + dc >= C[np]: continue C[np] = cc + dc Que.append(np) HL = HeavyLightDecomposition(E) q = int(input()) for _ in range(q): s, t = map(int, input().split()) st_lca = HL.lca(s, t) print(C[s] + C[t] - 2 * C[st_lca])