using System; using static System.Console; using System.Linq; using System.Collections.Generic; using System.Security.Cryptography; using Microsoft.VisualBasic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var n = NN; var map = NArr(n - 1); var q = NN; var query = NArr(q); var tree = new List<(int to, long w)>[n]; for (var i = 0; i < n; ++i) tree[i] = new List<(int to, long w)>(); foreach (var edge in map) { tree[edge[0]].Add((edge[1], edge[2])); tree[edge[1]].Add((edge[0], edge[2])); } var lca = new LCA(tree); var ans = new long[q]; for (var i = 0; i < q; ++i) { var x = query[i][0]; var y = query[i][1]; var z = query[i][2]; var xy = lca.Distance(x, y); var yz = lca.Distance(y, z); var zx = lca.Distance(z, x); ans[i] = Math.Min(xy.w + lca.Distance(xy.lca, z).w, Math.Min(yz.w + lca.Distance(yz.lca, x).w, zx.w + lca.Distance(zx.lca, y).w)); } WriteLine(string.Join("\n", ans)); } // 木の最小共通祖先(LCA)を求める // 頂点間の距離を高速に求める class LCA { int[] depth; long[] wdepth; List[] dmap; /// 辺の距離がすべて1のときのLCAを求められる初期設定 /// 木 public LCA(List[] tree) { depth = new int[tree.Length]; var maxDepth = DepthList(-1, 0, 0, tree); wdepth = new long[tree.Length]; for (var i = 0; i < tree.Length; ++i) wdepth[i] = depth[i]; dmap = new List[tree.Length]; for (var i = 0; i < dmap.Length; ++i) dmap[i] = new List(); for (var i = 0; i < dmap.Length; ++i) { var nx = -1; foreach (var next in tree[i]) if (depth[next] < depth[i]) nx = next; dmap[i].Add(nx); } for (int d = 2, j = 0; d <= maxDepth; d *= 2, ++j) for (var i = 0; i < dmap.Length; ++i) { var nx = -1; if (dmap[i][j] > -1) nx = dmap[dmap[i][j]][j]; dmap[i].Add(nx); } } /// 辺の距離が設定されているときのLCAを求められる初期設定 /// 木 public LCA(List<(int to, long w)>[] tree) { depth = new int[tree.Length]; wdepth = new long[tree.Length]; var maxDepth = DepthList(-1, 0, 0, tree); dmap = new List[tree.Length]; for (var i = 0; i < dmap.Length; ++i) dmap[i] = new List(); for (var i = 0; i < dmap.Length; ++i) { var nx = -1; foreach (var next in tree[i]) if (depth[next.to] < depth[i]) nx = next.to; dmap[i].Add(nx); } for (int d = 2, j = 0; d <= maxDepth; d *= 2, ++j) for (var i = 0; i < dmap.Length; ++i) { var nx = -1; if (dmap[i][j] > -1) nx = dmap[dmap[i][j]][j]; dmap[i].Add(nx); } } public (int d, long w, int lca) Distance(int x, int y) { var res = 0; if (depth[x] < depth[y]) (x, y) = (y, x); var xw = wdepth[x]; var yw = wdepth[y]; while (depth[x] > depth[y]) { for (var b = dmap[x].Count - 1; b >= 0; --b) { var move = 1 << b; if (depth[x] - depth[y] >= move) { x = dmap[x][b]; res += move; } } } for (var b = dmap[x].Count - 1; b >= 0; --b) { if (dmap[x][b] != dmap[y][b]) { x = dmap[x][b]; y = dmap[y][b]; res += 2 << b; } } var lca = x; if (x != y) { res += 2; lca = dmap[x][0]; } return (res, xw + yw - 2 * wdepth[lca], lca); } int DepthList(int prev, int cur, int d, List[] tree) { depth[cur] = d; var max = d; foreach (var next in tree[cur]) { if (next == prev) continue; max = Math.Max(max, DepthList(cur, next, d + 1, tree)); } return max; } int DepthList(int prev, int cur, int d, List<(int to, long w)>[] tree) { depth[cur] = d; var max = d; foreach (var next in tree[cur]) { if (next.to == prev) continue; wdepth[next.to] = wdepth[cur] + next.w; max = Math.Max(max, DepthList(cur, next.to, d + 1, tree)); } return max; } } }