from collections import deque class LowestCommonAncestor(): """根付き木に対して、二頂点の共通の祖先で最も近いところにある頂点を求める 初期化(ダブリング配列parent[k][v]の構築): O(NlogN) lcaを求めるクエリ: O(logN) """ def __init__(self, tree, root): self.n = len(tree) self.depth = [0] * self.n self.log_size = (self.n).bit_length() self.parent = [[-1] * self.n for i in range(self.log_size)] # 親を2^0回たどって到達する頂点、つまり現在の頂点に対する親の頂点を求める # parent[0][現在の頂点] = 親の頂点 q = deque([(root, -1, 0)]) # (現在の地点, 親の頂点, 現在の頂点と親の頂点間の距離) while q: v, par, dist = q.pop() self.parent[0][v] = par self.depth[v] = dist for child_v in tree[v]: if child_v != par: self.depth[child_v] = dist + 1 q.append((child_v, v, dist + 1)) # ダブリングで親を2^k回たどって到達する頂点を求める for k in range(1, self.log_size): for v in range(self.n): self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]] def lca(self, u, v): # u, vのうち深いところにある方から|depth[u] - depth[v]|だけ親をたどる if self.depth[u] > self.depth[v]: u, v = v, u for k in range(self.log_size): if (self.depth[v] - self.depth[u] >> k) & 1: v = self.parent[k][v] if u == v: return u # 二分探索でLCAを求める for k in reversed(range(self.log_size)): if self.parent[k][u] != self.parent[k][v]: u = self.parent[k][u] v = self.parent[k][v] return self.parent[0][u] def distance(tree_with_cost, root): dist2 = [0] * len(tree_with_cost) # 根からの距離を求める q = deque([(root, -1)]) # (現在の地点, 親の頂点) while q: v, par = q.pop() for child_v, cost in tree_with_cost[v]: if child_v != par: dist2[child_v] = dist2[v] + cost q.append((child_v, v)) return dist2 n = int(input()) info = [list(map(int, input().split())) for i in range(n-1)] tree = [[] for i in range(n)] tree_with_cost = [[] for i in range(n)] for i in range(n-1): a, b, cost = info[i] tree[a].append(b) tree[b].append(a) tree_with_cost[a].append((b, cost)) tree_with_cost[b].append((a, cost)) lca = LowestCommonAncestor(tree, 0) kyori = distance(tree_with_cost, 0) q = int(input()) query = [list(map(int, input().split())) for i in range(q)] for i in range(q): u, v, w = query[i] uv = kyori[u] + kyori[v] - 2* kyori[lca.lca(u, v)] vw = kyori[v] + kyori[w] - 2* kyori[lca.lca(v, w)] wu = kyori[w] + kyori[u] - 2* kyori[lca.lca(w, u)] print((uv+vw+wu)//2)