1 /**************************************************************  2     Problem: 2286  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:6148 ms  7     Memory:38896 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 typedef long long ll; 15 const int N = 250005; 16 const int M = N << 1; 17 const ll inf = (ll) 1e60; 18   19 struct edge { 20   int next, to, v; 21   edge() {} 22   edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 23 } e[M]; 24   25 struct Edge { 26   int next, to; 27   Edge() {} 28   Edge(int _n, int _t) : next(_n), to(_t) {} 29 } E[M]; 30   31 int first[N], First[N], tot; 32   33 struct tree_node { 34   int fa[19], dep, w; 35   ll mn; 36 } tr[N]; 37   38 int n, m, cnt_dfs; 39 int s[N], top; 40 ll f[N]; 41 int K; 42 int h[N], cnt_h; 43   44 int read() { 45   int x = 0; 46   char ch = getchar(); 47   while (ch < ‘0‘ || ‘9‘ < ch) 48     ch = getchar(); 49   while (‘0‘ <= ch && ch <= ‘9‘) 50     (x *= 10) += ch - ‘0‘, ch = getchar(); 51   return x; 52 } 53   54 inline bool cmp(int a, int b) { 55   return tr[a].w < tr[b].w; 56 } 57   58 inline void Add_Edges(int x, int y, int z) { 59   e[++tot] = edge(first[x], y, z), first[x] = tot; 60   e[++tot] = edge(first[y], x, z), first[y] = tot; 61 } 62   63 inline void add_edge(int x, int y) { 64   if (x == y) return; 65   E[++tot] = Edge(First[x], y), First[x] = tot; 66 } 67   68 #define y e[x].to 69 void dfs(int p) { 70   int x; 71   tr[p].w = ++cnt_dfs; 72   for (x = 1; x <= 18; ++x) 73     tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1]; 74   for (x = first[p]; x; x = e[x].next) 75     if (y != tr[p].fa[0]) { 76       tr[y].mn = min(tr[p].mn, (ll) e[x].v); 77       tr[y].dep = tr[p].dep + 1; 78       tr[y].fa[0] = p; 79       dfs(y); 80     } 81 } 82 #undef y 83   84 inline int get_lca(int x, int y) { 85   int i; 86   if (tr[x].dep < tr[y].dep) swap(x, y); 87   for (i = 18; ~i; --i) 88     if (tr[tr[x].fa[i]].dep >= tr[y].dep) x = tr[x].fa[i]; 89   if (x == y) return x; 90   for (i = 18; ~i; --i) 91     if (tr[x].fa[i] != tr[y].fa[i]) 92       x = tr[x].fa[i], y = tr[y].fa[i]; 93   return tr[x].fa[0]; 94 } 95   96 #define y E[x].to 97 void dp(int p) { 98   ll tmp = 0; 99   int x;100   for (x = First[p]; x; x = E[x].next)101     dp(y), tmp += f[y];102   First[p] = 0;103   f[p] = (tmp != 0 && tmp <= tr[p].mn ? tmp : tr[p].mn);104 }105 #undef y106  107 void work() {108   int i, now, lca;109   K = read(), tot = 0;110   for (i = 1; i <= K; ++i) h[i] = read();111   sort(h + 1, h + K + 1, cmp);112   for (cnt_h = 1, i = 2; i <= K; ++i)113     if (get_lca(h[cnt_h], h[i]) != h[cnt_h]) h[++cnt_h] = h[i];114   s[top = 1] = 1;115   for (i = 1; i <= cnt_h; ++i) {116     now = h[i], lca = get_lca(now, s[top]);117     while (1) {118       if (tr[lca].dep >= tr[s[top - 1]].dep) {119     add_edge(lca, s[top--]);120     if (s[top] != lca) s[++top] = lca;121     break;122       }123       add_edge(s[top - 1], s[top]);124       --top;125     }126     if (s[top] != now) s[++top] = now;127   }128   while (--top) add_edge(s[top], s[top + 1]);129   dp(1);130   printf("%lld\n", f[1]);131 }132  133 int main() {134   int i, x, y, z;135   n = read();136   for (i = 1; i < n; ++i) {137     x = read(), y = read(), z = read();138     Add_Edges(x, y, z);139   }140   tr[1].mn = inf, tr[1].dep = 1;141   dfs(1);142   m = read();143   while (m--) work();144   return 0;145 }