using System; using static System.Console; using System.Linq; using System.Collections.Generic; 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 len)>[n]; for (var i = 0; i < n; ++i) tree[i] = new List<(int to, long len)>(); foreach (var edge in map) { tree[edge[0]].Add((edge[1], edge[2])); tree[edge[1]].Add((edge[0], edge[2])); } var order = new List(n); DFS(0, -1, tree, order); var posorder = new int[n]; for (var i = 0; i < n; ++i) posorder[order[i]] = i; var lca = new LCA(tree); var ans = new long[q]; for (var i = 0; i < q; ++i) { var list = new List<(int id, int ord)>(query[i].Length); for (var j = 1; j < query[i].Length; ++j) list.Add((query[i][j], posorder[query[i][j]])); list.Sort((l, r) => l.ord.CompareTo(r.ord)); var infolist = new List(); var t = new AvlTree(); var pq = new PriorityQueue(); for (var j = 1; j < list.Count; ++j) { var dist = lca.Distance(list[j - 1].id, list[j].id); var info = new Info(j - 1, list[j - 1].id, list[j].id, dist.lca, posorder[list[j - 1].id], dist.w); infolist.Add(info); t.Insert(info); pq.Enqueue(info, -lca.GetDepth(info.Lca)); } // WriteLine(string.Join(" ", infolist)); while (pq.Count > 0) { var info = pq.Dequeue(); if (info.Deleted) continue; ans[i] += info.Len; var ipos = 0; t.LowerBound(info, ref ipos); Info ins1 = null; if (ipos > 0) { var left = t.ElementAt(ipos - 1); t.Delete(left); left.Deleted = true; var dist = lca.Distance(left.Left, info.Lca); ins1 = new Info(infolist.Count, left.Left, info.Lca, dist.lca, posorder[left.Left], dist.w); } Info ins2 = null; if (ipos + 1 < t.GetCount()) { var right = t.ElementAt(ipos + 1); t.Delete(right); right.Deleted = true; var dist = lca.Distance(info.Lca, right.Right); ins2 = new Info(infolist.Count + (ins1 == null ? 0 : 1), info.Lca, right.Right, dist.lca, posorder[info.Lca], dist.w); } t.Delete(info); // WriteLine($"out : {info}"); if (ins1 != null) { infolist.Add(ins1); t.Insert(ins1); pq.Enqueue(ins1, -lca.GetDepth(ins1.Lca)); // WriteLine($"in : {ins1}"); } if (ins2 != null) { infolist.Add(ins2); t.Insert(ins2); pq.Enqueue(ins2, -lca.GetDepth(ins2.Lca)); // WriteLine($"in : {ins2}"); } } } WriteLine(string.Join("\n", ans)); } class Info : IComparable { public int Id; public int Left; public int Right; public int Lca; public int LeftOrd; public long Len; public bool Deleted; public Info(int id, int left, int right, int lca, int leftord, long len) { Id = id; Left = left; Right = right; Lca = lca; LeftOrd = leftord; Len = len; } public int CompareTo(Info b) { return LeftOrd.CompareTo(b.LeftOrd); } public override string ToString() { return $"({Id}, {Left}, {Right}, {Lca}, {LeftOrd}, {Len}, {Deleted})"; } } static void DFS(int cur, int prev, List<(int to, long len)>[] tree, List order) { order.Add(cur); foreach (var next in tree[cur]) { if (next.to == prev) continue; DFS(next.to, cur, tree, order); } } 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); } public int GetDepth(int cur) { return depth[cur]; } 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; } } public class AvlTree where T: IComparable { private class Node where U: IComparable { public U Value; public Node Lc = null; public Node Rc = null; public int Height; public int Count; public int CCount; public Node(int height, U value) { Height = height; Count = 1; CCount = 1; Value = value; } } private Node root = null; static int GetHeight(Node t) { return t == null ? 0 : t.Height; } static int GetCount(Node t) { return t == null ? 0 : t.Count; } static int GetBalance(Node t) { return GetHeight(t.Lc) - GetHeight(t.Rc); } static void Recalc(Node t) { if (t == null) return; t.Height = 1 + Math.Max(GetHeight(t.Lc), GetHeight(t.Rc)); t.Count = t.CCount + GetCount(t.Lc) + GetCount(t.Rc); } static Node RotateLeft(Node t) { Node u = t.Rc; Node t2 = u.Lc; u.Lc = t; t.Rc = t2; Recalc(t); Recalc(u); return u; } static Node RotateRight(Node t) { Node u = t.Lc; Node t2 = u.Rc; u.Rc = t; t.Lc = t2; Recalc(t); Recalc(u); return u; } static Node RotateLR(Node t) { t.Lc = RotateLeft(t.Lc); return RotateRight(t); } static Node RotateRL(Node t) { t.Rc = RotateRight(t.Rc); return RotateLeft(t); } static Node BalanceLeft(Node t) { if (GetBalance(t) > 1) { if (GetBalance(t.Lc) < 0) t = RotateLR(t); else t = RotateRight(t); } Recalc(t); return t; } static Node BalanceRight(Node t) { if (GetBalance(t) < -1) { if (GetBalance(t.Rc) > 0) t = RotateRL(t); else t = RotateLeft(t); } Recalc(t); return t; } /// valueを挿入する public void Insert(T value) { root = Insert(root, value); } Node Insert(Node cur, T value) { if (cur == null) { return new Node(1, value); } var d = value.CompareTo(cur.Value); if (d < 0) { cur.Lc = Insert(cur.Lc, value); return BalanceLeft(cur); } else if (d > 0) { cur.Rc = Insert(cur.Rc, value); return BalanceRight(cur); } else { ++cur.CCount; Recalc(cur); return cur; } } /// valueを削除する 存在しない場合はなにもしない public void Delete(T value) { root = Delete(root, value); } Node Delete(Node cur, T value) { if (cur == null) return null; var d = value.CompareTo(cur.Value); if (d < 0) { cur.Lc = Delete(cur.Lc, value); return BalanceRight(cur); } else if (d > 0) { cur.Rc = Delete(cur.Rc, value); return BalanceLeft(cur); } else { --cur.CCount; if (cur.CCount == 0) { if (cur.Lc != null) { Node del = null; var max = DeleteMax(cur.Lc, ref del); cur.Lc = max; cur.Value = del.Value; cur.CCount = del.CCount; return BalanceRight(cur); } else { return cur.Rc; } } else { Recalc(cur); return cur; } } } Node DeleteMax(Node t, ref Node del) { if (t.Rc == null) { del = t; return t.Lc; } else { var max = DeleteMax(t.Rc, ref del); t.Rc = max; return BalanceLeft(t); } } /// 小さいほうからpos番目の要素を取得する public T ElementAt(int pos) { if (pos < 0 || pos >= GetCount(root)) return default; var t = ElementAt(root, pos); return t.Value; } /// 小さいほうからpos番目の要素を取得する public T ElementAt(int pos, T defaultValue) { if (pos < 0 || pos >= GetCount(root)) return defaultValue; return ElementAt(pos); } Node ElementAt(Node cur, int pos) { if (pos < GetCount(cur.Lc)) return ElementAt(cur.Lc, pos); if (pos < GetCount(cur.Lc) + cur.CCount) return cur; if (pos < cur.Count) return ElementAt(cur.Rc, pos - GetCount(cur.Lc) - cur.CCount); return null; } public void Debug() { if (root == null) return; Console.WriteLine($"root val:{root.Value}, CCount:{root.CCount}, Count:{root.Count}"); Debug(root.Value, root.Lc); Debug(root.Value, root.Rc); } void Debug(T pval, Node cur) { if (cur == null) return; Console.WriteLine($"{pval} -> val:{cur.Value}, CCount:{cur.CCount}, Count:{cur.Count}"); Debug(cur.Value, cur.Lc); Debug(cur.Value, cur.Rc); } /// value以上でもっとも小さい値とその場所を返却する そのようなものが存在しなければデフォルト値を返す public T LowerBound(T value, ref int index) { var cur = root; T ans = default; var add = 0; index = GetCount(root); while (cur != null) { if (value.CompareTo(cur.Value) <= 0) { ans = cur.Value; index = add + GetCount(cur.Lc); cur = cur.Lc; } else { add += GetCount(cur.Lc) + cur.CCount; cur = cur.Rc; } } return ans; } /// 要素の個数を求める public int GetCount() { return GetCount(root); } /// 要素の一覧を返す public List GetValues() { var list = new List(); if (root != null) GetValues(root, list); return list; } static void GetValues(Node cur, List list) { if (cur.Lc != null) GetValues(cur.Lc, list); list.Add(cur.Value); if (cur.Rc != null) GetValues(cur.Rc, list); } /// 指定された要素が存在するか求める /// /// public bool Contains(T value) { if (root == null) return false; return Contains(root, value); } static bool Contains(Node cur, T value) { var d = cur.Value.CompareTo(value); if (d == 0) return true; if (d > 0) { if (cur.Lc == null) return false; return Contains(cur.Lc, value); } else { if (cur.Rc == null) return false; return Contains(cur.Rc, value); } } } }