传送门
SOL
建棵虚树dp即可；
一、此题有两个优化
1： 把边权转成点权，但由于此题需要与根断开，所以直接把根到点路径上最小边权转化成点权即可
2： 虚树中，只需要“最上面”的点即可。即 对于 每一个关键点 如果 其 祖先 也在虚树中 就 不需要加入虚树(因为祖先必须断开，下面的点没有讨论价值）
二、dp方程含义： dp(i) ：把 i的子树与i断开的最小代价
注意lca不要写挂！！
CODE
#include<bits/stdc++.h>
using namespace std
;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define in red()
#define ll long long
inline int red()
{
int data
=0;int w
=1; char ch
=0;
ch
=getchar();
while(ch
!='-' && (ch
<'0' || ch
>'9')) ch
=getchar();
if(ch
=='-') w
=-1,ch
=getchar();
while(ch
>='0' && ch
<='9') data
=(data
<<3)+(data
<<1)+ch
-'0',ch
=getchar();
return data
*w
;
}
const int maxn
=3e5+10;
int nxt
[maxn
<<1],to
[maxn
<<1],head
[maxn
],w
[maxn
<<1],dfn
[maxn
],tim
,val
[maxn
],n
,cnt
=0;
int st
[maxn
<<1][25],tot
=0,lg
[maxn
<<1],pos
[maxn
];
typedef pair
<int,int> T
;
inline int _min(int a
,int b
){
return dfn
[a
]<dfn
[b
] ? a
: b
;
}
vector
<int> G
[maxn
];
inline void _add(int u
,int v
,int _w
){
nxt
[++cnt
]=head
[u
];head
[u
]=cnt
;to
[cnt
]=v
;w
[cnt
]=_w
;
}
void dfs(int u
,int f
){
dfn
[u
]=++tim
;st
[++tot
][0]=u
;pos
[u
]=tot
;
for(int i
=head
[u
];i
;i
=nxt
[i
]){
if(to
[i
]^f
){
val
[to
[i
]]=u
^1? min(val
[u
],w
[i
]) : w
[i
];
dfs(to
[i
],u
);
st
[++tot
][0]=u
;
}
}
}
inline void pre(){
lg
[1]=0;
for(int i
=2;i
<=tot
;++i
)lg
[i
]=lg
[i
>>1]+1;
for(int j
=1;(1<<j
)<=tot
;++j
){
for(int i
=1;i
+(1<<j
)-1<=tot
;++i
){
st
[i
][j
]=_min(st
[i
][j
-1],st
[i
+(1<<j
-1)][j
-1]);
}
}
}
inline int lca(int u
,int v
){
int x
=pos
[u
],y
=pos
[v
];
if(x
>y
)swap(x
,y
);
int k
=lg
[y
-x
+1];
return _min(st
[x
][k
],st
[y
-(1<<k
)+1][k
]);
}
int stk
[maxn
],top
=0;
T pi
[maxn
];
inline void addedge(int u
,int v
){
G
[u
].push_back(v
);
}
inline void insert(int u
){
if(top
<=1){stk
[++top
]=u
;return;}
int f
=lca(stk
[top
],u
);
if(f
==stk
[top
])return;
while(top
>1&&dfn
[stk
[top
-1]]>=dfn
[f
])addedge(stk
[top
-1],stk
[top
]),--top
;
if(stk
[top
]!=f
)addedge(f
,stk
[top
]),stk
[top
]=f
;
stk
[++top
]=u
;
}
ll
dp(int u
){
ll res
=0;
for(int i
=0;i
<G
[u
].size();++i
){
int v
=G
[u
][i
];
ll k
=dp(v
);
res
+= k
? min(k
,1ll*val
[v
]) : val
[v
];
}
G
[u
].clear();
return res
;
}
signed main(){
n
=in
;
for(int i
=1;i
<n
;++i
){
int u
=in
,v
=in
,_w
=in
;
_add(u
,v
,_w
);_add(v
,u
,_w
);
}
dfs(1,0);
pre();
int m
=in
;
stk
[top
=1]=1;
while(m
--){
int k
=in
;
for(int i
=1;i
<=k
;++i
)pi
[i
].se
=in
,pi
[i
].fi
=dfn
[pi
[i
].se
];
sort(pi
+1,pi
+k
+1);
for(int i
=1;i
<=k
;++i
)insert(pi
[i
].se
);
while(top
>1)addedge(stk
[top
-1],stk
[top
]),--top
;
cout
<<dp(1)<<'\n';
}
return 0;
}
