题面：
思路：
看到所有询问中的点数总和是十万级别的，就想到用虚树~(≧▽≦)/~啦
首先，树形dp应该是很明显可以看出来的：
设dp[u]表示以u为根的子树（不包括u）中的宝藏岛全部切断的最小需要值
那么显然dp[u]等于所有dp[v]的和（v是u的儿子）与从根（一号结点）到u的路径上的最小边权之间的最小值
然后dp[1]就是答案了
建出虚树然后dp，$Oleft(n ight)$解决
Code：
1 /#include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cassert> 6 #define ll long long 7 using namespace std; 8 const long long inf=(1ll<<50ll); 9 inline ll read(){ 10 ll re=0,flag=1;char ch=getchar(); 11 while(ch>'9'||ch<'0'){ 12 if(ch=='-') flag=-1; 13 ch=getchar(); 14 } 15 while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar(); 16 return re*flag; 17 } 18 ll n,m,dep[250010],fa[250010],st[250010][20],dfn[250010],clk,minn[250010]; 19 struct graph{ 20 ll first[250010],cnt; 21 struct edge{ 22 ll to,next,w; 23 }a[500010]; 24 inline void add(ll u,ll v,ll w){ 25 if(u==v) return; 26 a[++cnt]=(edge){v,first[u],w};first[u]=cnt; 27 } 28 void init(){ 29 cnt=0; 30 } 31 }G,g; 32 void dfs(ll u,ll f){ 33 ll i,v;fa[u]=st[u][0]=f;dfn[u]=++clk;dep[u]=dep[f]+1; 34 for(i=G.first[u];~i;i=G.a[i].next){ 35 v=G.a[i].to; 36 if(v==f) continue; 37 minn[v]=min(minn[u],G.a[i].w); 38 dfs(v,u); 39 } 40 } 41 void ST(){ 42 ll i,j; 43 for(j=1;j<=19;j++){ 44 for(i=1;i<=n;i++) st[i][j]=st[st[i][j-1]][j-1]; 45 } 46 } 47 ll lca(ll l,ll r){ 48 if(dep[l]>dep[r]) swap(l,r); 49 ll i; 50 for(i=19;i>=0;i--) if(dep[st[r][i]]>=dep[l]) r=st[r][i]; 51 if(l==r) return l; 52 for(i=19;i>=0;i--) 53 if(st[l][i]!=st[r][i]){ 54 l=st[l][i]; 55 r=st[r][i]; 56 } 57 return fa[l]; 58 } 59 ll q[250010],tot,s[250010],top,num,f[250010]; 60 bool cmp(ll l,ll r){ 61 return dfn[l]<dfn[r]; 62 } 63 void dp(ll u){ 64 ll i,v,tmp=0; 65 for(i=g.first[u];~i;i=g.a[i].next){ 66 v=g.a[i].to;g.first[u]=g.a[i].next; 67 dp(v);tmp+=f[v]; 68 } 69 if(!tmp) f[u]=minn[u]; 70 else f[u]=min(minn[u],tmp); 71 } 72 int main(){ 73 ll i,t1,t2,t3,j; 74 n=read();memset(G.first,-1,sizeof(G.first)); 75 for(i=1;i<n;i++){ 76 t1=read();t2=read();t3=read(); 77 G.add(t1,t2,t3);G.add(t2,t1,t3); 78 } 79 minn[1]=inf; 80 dfs(1,0);ST(); 81 m=read();memset(g.first,-1,sizeof(g.first)); 82 for(i=1;i<=m;i++){ 83 tot=read();//memset(q,0,sizeof(q)); 84 for(j=1;j<=tot;j++) q[j]=read(),assert(q[j]<=n); 85 sort(q+1,q+tot+1,cmp);g.init(); 86 num=0;q[++num]=q[1]; 87 for(j=2;j<=tot;j++) if(lca(q[j],q[num])!=q[num]) q[++num]=q[j]; 88 s[++top]=1;ll grand; 89 for(j=1;j<=num;j++){ 90 if(q[j]==0) return *(int*)0; 91 grand=lca(q[j],s[top]); 92 while(1){ 93 if(dep[s[top-1]]<=dep[grand]){ 94 g.add(grand,s[top--],0); 95 if(s[top]!=grand) s[++top]=grand; 96 break; 97 } 98 g.add(s[top-1],s[top],0);top--; 99 } 100 if(s[top]!=q[j]) s[++top]=q[j]; 101 } 102 while(--top) g.add(s[top],s[top+1],0); 103 dp(1); 104 printf("%lld ",f[1]); 105 } 106 }