谢谢啦~
#include<bits/stdc++.h>
#define int long long
using namespace std;
//取宏定义
const int INF=0x7ffff;
const int M=2e5+5e4+110;
//快读
inline int read(){
int sum=0,k=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')k=-1;c=getchar();
}while(c>='0'&&c<='9'){sum=sum*10+c-48; c=getchar();
}return sum*k;
}
//原图的链式前向星
int Head[M],Tot=0;
struct Line_Node{
int Next,To,Val;
}Ed[M<<2];
inline void Adde(int u,int v,int w){
Ed[++Tot]={Head[u],v,w};
Head[u]=Tot;
}
//树剖预处理结点权值与LCA
int va[M];
int Fa[M],Siz[M],Son[M],Deep[M];
//第一遍dfs
inline void dfs1(int u,int fa){
Fa[u]=fa;Siz[u]=1;//记录父亲与子树大小
Deep[u]=Deep[fa]+1;//记录深度
for(int i=Head[u];i;i=Ed[i].Next){
int v=Ed[i].To;
if(v==fa) continue;
va[v]=min(va[u],Ed[i].Val);//结点权值
dfs1(v,u);
if(Siz[v]>Siz[Son[u]]) Son[u]=v;//重儿子
Siz[u]+=Siz[v];
}
}
//第二次dfs
int Tim=0;
int Id[M],Top[M];
inline void dfs2(int u,int topf){
Id[u]=++Tim;Top[u]=topf;//dfs序
if(!Son[u]) return ;
dfs2(Son[u],topf);
for(int i=Head[u];i;i=Ed[i].Next){
int v=Ed[i].To;
if(v==Fa[u]) continue;
if(v==Son[u]) continue;
dfs2(v,v);//向下搜
}
}//处理LCA 对了版子
inline int Get_LCA(int a,int b){
while(Top[a]!=Top[b]){
if(Deep[Top[a]]<Deep[Top[b]]) swap(a,b);
a=Fa[Top[a]];
}if(Deep[a]<Deep[b]) swap(a,b);
return b;
}
//struct virtual_tree{
// int Next,To;
//}Ved[M];
//int Vhead[M],Vtot=0;
//inline void Vadde(int u,int v){
// Ved[++Vtot]={Vhead[u],v};
// Vhead[u]=Vtot;
//}
vector<int>e[M];//虚树边
inline void Vadde(int u,int v){
e[u].push_back(v);
}
int top=0;//手写栈
int Sta[M];
inline void Insert(int u){//插入
if(top==1){Sta[++top]=u;return ;}//栈中只有一个结点
int lca=Get_LCA(u,Sta[top]);//搞个LCA
if(lca==Sta[top]) return ;
while(top>1&&Id[Sta[top-1]>=Id[lca]])
Vadde(Sta[top-1],Sta[top]),top--;
if(lca!=Sta[top]) Vadde(lca,Sta[top]),Sta[top]=lca;
Sta[++top]=u;
}
inline int Get_Dp(int u){
if(e[u].size()==0) return va[u];//本来就是空的
int sum=0;//累加
for(auto v:e[u])
sum+=Get_Dp(v);
e[u].clear();//清空
return min(sum,va[u]);//dp嘛
}
int a[M];//存关键点
inline bool cmp(const int &a,const int &b){
return Id[a]<Id[b];//按照dfs序排
}
signed main(){
int n=read();va[1]=INF;
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
Adde(u,v,w);Adde(v,u,w);
}
dfs1(1,0);dfs2(1,1);
int m=read();
while(m--){
int k=read();
for(int i=1;i<=k;i++) a[i]=read();
sort(a+1,a+1+k,cmp);
Sta[top=1]=1;
// cout<<'\n';
// for(int i=1;i<=k;i++) cout<<" "<<a[i]<<" ";
// cout<<'\n';
for(int i=1;i<=k;i++) Insert(a[i]);
while(top>0) Vadde(Sta[top-1],Sta[top]),top--;
printf("%lld\n",Get_Dp(1));
}
return 0;
}
/*
10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6
*/