1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, uu, vv, ww, hea[250005], cnt, dfn[250005], fa[250005][19];
int mn[250005][19], idx, vr, ki, wht[250005], nxg[250005], din;
int sta[250005], par[250005], dep[250005], qwq[250005];
ll dp[250005];
bool isw[250005];
const int oo=0x3f3f3f3f;
struct Edge{
int too, nxt, val;
}edge[500005];
void add_edge(int fro, int too, int val){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
edge[cnt].val = val;
hea[fro] = cnt;
}
void dfs(int x, int f){
dfn[x] = ++idx;
fa[x][0] = f;
dep[x] = dep[f] + 1;
for(int i=1; i<=17; i++){
fa[x][i] = fa[fa[x][i-1]][i-1];
mn[x][i] = min(mn[x][i-1], mn[fa[x][i-1]][i-1]);
}
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f){
mn[t][0] = edge[i].val;
dfs(t, x);
}
}
}
bool cmp(int x, int y){
return dfn[x]<dfn[y];
}
int getLca(int x, int y){
if(dep[x]<dep[y]) swap(x, y);
for(int i=17; i>=0; i--)
if(dep[fa[x][i]]>=dep[y])
x = fa[x][i];
if(x==y) return x;
for(int i=17; i>=0; i--)
if(fa[x][i]!=fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
int getMin(int x, int y){
int re=oo;
for(int i=17; i>=0; i--)
if(dep[fa[x][i]]>=dep[y]){
re = min(re, mn[x][i]);
x = fa[x][i];
}
return re;
}
void build(){
din = 0;
sort(wht+1, wht+1+vr, cmp);
int tmp=vr;
for(int i=1; i<=tmp; i++){
int x=wht[i];
if(!din){
par[x] = 0;
sta[++din] = x;
}
else{
int lca=getLca(sta[din], x);
while(dep[sta[din]]>dep[lca]){
if(dep[sta[din-1]]<dep[lca]) par[sta[din]] = lca;
din--;
}
if(lca!=sta[din]){
wht[++vr] = lca;
par[lca] = sta[din];
sta[++din] = lca;
}
par[x] = lca; sta[++din] = x;
}
}
sort(wht+1, wht+1+vr, cmp);
}
ll solve(){
build();
for(int i=2; i<=vr; i++)
qwq[wht[i]] = getMin(wht[i], par[wht[i]]);
for(int i=1; i<=vr; i++)
dp[wht[i]] = 0;
for(int i=vr; i>=2; i--){
int x=wht[i];
if(isw[x]) dp[par[x]] += qwq[x];
else dp[par[x]] += min((ll)qwq[x], dp[x]);
}
return dp[1];
}
int main(){
cin>>n;
for(int i=1; i<n; i++){
scanf("%d %d %d", &uu, &vv, &ww);
add_edge(uu, vv, ww);
add_edge(vv, uu, ww);
}
dfs(1, 0);
cin>>m;
while(m--){
vr = 0;
scanf("%d", &ki);
wht[++vr] = 1;
for(int i=1; i<=ki; i++){
scanf("%d", &nxg[i]);
wht[++vr] = nxg[i];
isw[nxg[i]] = true;
}
printf("%lld\n", solve());
for(int i=1; i<=ki; i++)
isw[nxg[i]] = false;
}
return 0;
}
|