#include #include #include #include #define llint long long #define inf 1e18 using namespace std; struct edge{ llint to, cost; edge(){} edge(llint a, llint b){ to = a, cost = b; } }; typedef pair P; struct HLD{ int V, logV; vector

mp; map mp2; vector

parent; //subtree of v is [pre_order[v], back_order[v]] vector pre_order; vector back_order; int order; int global_id, local_id; vector size, depth; vector > prev; HLD(){} void predfs(vector G[], int v, int p, int d) { size[v] = 1, depth[v] = d, prev[v][0] = p; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == p) continue; predfs(G, G[v][i], v, d+1); size[v] += size[G[v][i]]; } } void maindfs(vector G[], int v, int p) { mp[v] = make_pair(global_id, local_id); mp2[make_pair(global_id, local_id)] = v; pre_order[v] = ++order; if(G[v].size() == 1 && G[v][0] == p){ back_order[v] = order; return; } vector

vec; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == p) continue; vec.push_back(make_pair(size[G[v][i]], G[v][i])); } sort(vec.rbegin(), vec.rend()); local_id++; if(vec.size() >= 1) maindfs(G, vec[0].second, v); for(int i = 1; i < vec.size(); i++){ parent.push_back(mp[v]); global_id++, local_id = 0; maindfs(G, vec[i].second, v); } back_order[v] = order; } int getLCA(int u, int v){ int x = u, y = v; if(depth[y] > depth[x]) swap(x, y); for(int i = logV-1; i >= 0; i--){ if(depth[x] - (1<= depth[y]) x = prev[x][i]; } if(x == y) return x; for(int i = logV-1; i >= 0; i--){ if(prev[x][i] != prev[y][i]){ x = prev[x][i]; y = prev[y][i]; } } x = prev[x][0]; return x; } void pathcalc(int v, int lca, vector > &dest) { int gid = mp[v].first, lid = mp[v].second; int Gid = mp[lca].first, Lid = mp[lca].second; while(Gid != gid){ dest.push_back(make_pair(gid, make_pair(0, lid))); int ngid = parent[gid].first, nlid = parent[gid].second; gid = ngid, lid = nlid; } dest.push_back(make_pair(gid, make_pair(Lid, lid))); } void init(vector G[], int V) // The tree must be 1-indexed. { this->V = V, logV = 0; for(int t = V; t; t/=2) logV++; prev.resize(V+1); for(int i = 0; i <= V; i++) prev[i].resize(logV); size.resize(V+1), depth.resize(V+1); predfs(G, 1, 0, 0); prev[0][0] = 0; for(int i = 1; i < logV; i++){ for(int j = 1; j <= V; j++){ prev[j][i] = prev[prev[j][i-1]][i-1]; } } mp.resize(V+1), mp2.clear(); parent.clear(), parent.push_back(make_pair(-1, -1)); pre_order.resize(V+1), back_order.resize(V+1); global_id = local_id = 0, order = 0; maindfs(G, 1, 0); } void path(int u, int v, vector > &dest) { dest.clear(); int lca = getLCA(u, v); pathcalc(u, lca, dest); pathcalc(v, lca, dest); pair p = make_pair(mp[lca].first, make_pair(mp[lca].second, mp[lca].second)); for(int i = 0; i < dest.size(); i++){ if(dest[i] == p){ dest.erase(dest.begin()+i); return ; } } } void toOrder(vector > &src, vector

&dest) { dest.clear(); for(int i = 0; i < src.size(); i++){ int u = mp2[make_pair(src[i].first, src[i].second.first)], v = mp2[make_pair(src[i].first, src[i].second.second)]; dest.push_back(make_pair(pre_order[u], pre_order[v])); } } }; llint n, Q; vector G[100005]; vector g[100005]; llint dist[100005]; HLD hld; void dfs(int v, int p, llint d) { dist[v] = d; for(int i = 0; i < g[v].size(); i++){ if(g[v][i].to == p) continue; dfs(g[v][i].to, v, d + g[v][i].cost); } } llint calc(llint s, llint t) { llint lca = hld.getLCA(s, t); return dist[s] + dist[t] - 2 * dist[lca]; } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; llint u, v, w; for(int i = 1; i <= n-1; i++){ cin >> u >> v >> w; u++, v++; G[u].push_back(v); G[v].push_back(u); g[u].push_back(edge(v, w)); g[v].push_back(edge(u, w)); } hld.init(G, n); dfs(1, -1, 0); cin >> Q; for(int q = 0; q < Q; q++){ llint k, x; vector

vec; cin >> k; for(int i = 0; i < k; i++){ cin >> x; x++; vec.push_back(make_pair(hld.pre_order[x], x)); } sort(vec.begin(), vec.end()); llint ans = 0; for(int i = 0; i < k; i++){ ans += calc(vec[i].second, vec[(i+1)%k].second); } cout << ans/2 << "\n"; } flush(cout); return 0; }