10pts 求条

#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout);
int n, q, m, a[500001];
bool imp[250001];
long long value[250001], dp[250001];
int fa[250001], depth[250001], son[250001], sz[250001], head[250001], dfn[250001], ddfn[250001], tot;
vector <pair <int, long long> > e[250001];
vector <int> g[250001];
int hi[500001];
long long mi[19], ST[250001][19];
void dfs1(int x, int father, int dep){
	fa[x] = father;
	depth[x] = dep;
	sz[x] = 1;
	for (pair <int, long long> u : e[x]){
		if (u.first == father){
			continue;
		}
		value[u.first] = u.second;
		dfs1(u.first, x, dep + 1);
		sz[x] += sz[u.first];
		if (sz[u.first] > sz[son[x]]){
			son[x] = u.first;
		}
	}
	return;
}
void dfs2(int x, int he){
	dfn[x] = ++tot;
	ddfn[tot] = x;
	head[x] = he;
	if (son[x]){
		dfs2(son[x], he);
		for (pair <int, long long> u : e[x]){
			if (u.first == fa[x] || u.first == son[x]){
				continue;
			}
			dfs2(u.first, u.first);
		}
	}
	return;
}
int lca(int u, int v){
	while (head[u] != head[v]){
		if (depth[head[u]] < depth[head[v]]){
			swap(u, v);
		}
		u = fa[head[u]];
	}
	if (depth[u] > depth[v]){
		swap(u, v);
	}
	return u;
}
long long qmin(int l, int r){
	return min(ST[l][hi[r - l + 1]], ST[r - (1 << hi[r - l + 1]) + 1][hi[r - l + 1]]);
}
long long querymin(int u, int v){
	long long res = 1e18;
	while (head[u] != head[v]){
		if (depth[head[u]] < depth[head[v]]){
			swap(u, v);
		}
		res = min(res, qmin(dfn[head[u]], dfn[u]));
		u = fa[head[u]];
	}
	if (u == v){
		return res;
	}
	if (depth[u] > depth[v]){
		swap(u, v);
	}
	res = min(res, qmin(dfn[u] + 1, dfn[v]));
	return res;
}
bool cmp(int x, int y){
	return dfn[x] < dfn[y];
}
void buildVT(){
	for (int i = 1; i <= n; i++){
		while (!g[i].empty()){
			g[i].pop_back();
		}
	}
	sort(a + 1, a + m + 1, cmp);
	int tmp = m;
	for (int i = 2; i <= tmp; i++){
		a[++m] = lca(a[i - 1], a[i]);
	}
	a[++m] = 1;
	sort(a + 1, a + m + 1, cmp);
	m = unique(a + 1, a + m + 1) - a - 1;
	for (int i = 2; i <= m; i++){
		g[lca(a[i - 1], a[i])].push_back(a[i]);
	}
	return;
}
void calc(int x){
	dp[x] = 0;
	for (int u : g[x]){
		calc(u);
		if (imp[u]){
			dp[x] += querymin(x, u);
		} else {
			dp[x] += min(dp[u], querymin(x, u));
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int u, v;
	long long w;
	cin >> n;
	for (int i = 1; i < n; i++){
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	mi[0] = 1;
	hi[1] = 0;
	for (int i = 1; i <= 18; i++){
		mi[i] = mi[i - 1] << 1;
		for (int j = mi[i - 1] + 1; j <= mi[i]; j++){
			hi[j] = i;
		}
	}
	for (int i = 1; i <= n; i++){
		ST[i][0] = value[ddfn[i]];
	}
	for (int j = 1; j <= 18; j++){
		for (int i = 1; i <= n; i++){
			ST[i][j] = min(ST[i][j - 1], ST[i + mi[j - 1]][j - 1]);
		}
	}
	cin >> q;
	while (q--){
		cin >> m;
		for (int i = 1; i <= m; i++){
			cin >> a[i];
			imp[a[i]] = true;
		}
		buildVT();
		calc(1);
		cout << dp[1] << "\n";
		for (int i = 1; i <= m; i++){
			imp[a[i]] = false;
		}
	}
	return 0;
}