【题目来源】
https://www.luogu.com.cn/problem/P2495
https://www.acwing.com/problem/content/2516/
【题目描述】
在一场战争中，战场由 n 个岛屿和 n-1 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 1 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 k 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 1 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 m 次，所以我们只需要把每次任务完成即可。
【输入格式】
第一行一个整数 n，表示岛屿数量。
接下来 n-1 行，每行三个整数 u，v，w，表示 u 号岛屿和 v 号岛屿由一条代价为 w 的桥梁直接相连。
第 n+1 行，一个整数 m，代表敌方机器能使用的次数。
接下来 m 行，第 i 行一个整数 k，代表第 i 次后，有 k 个岛屿资源丰富。接下来 ki 个整数 h1，h2，….，hk，表示资源丰富岛屿的编号。
【输出格式】
输出共 m 行，表示每次任务的最小代价。
【输入样例】
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
【输出样例】
12
32
22
【数据范围】
对于 10% 的数据，n≤10，m≤5。
对于 20% 的数据，n≤100，m≤100，1≤ki≤10。
对于 40% 的数据，n≤1000，1≤ki≤15。
对于100%的数据，2≤n≤2.5×10^5，1≤m≤5×10^5，Σki≤5×10^5，1≤ki<n，hi≠1，1≤u, v≤n，1≤w≤10^5。
【算法分析】
● 虚树是一种在树形结构问题中用于压缩规模、降低时间复杂度的数据结构，核心思想是只保留问题相关的关键节点，以及这些节点之间的路径关系，从而忽略大量无关节点，让原本无法在大数据范围下运行的算法变得可行。
（1）虚树的核心作用
虚树是临时数据结构，每组询问都需要根据查询节点重新构建，用完即弃。
对一棵 n 量级很大的树（如 1e5/1e6），每次查询只涉及 k 个关键点（k≪n），虚树可以只保留这些关键点间两两的 LCA，构建一棵节点数为 O(k) 的精简树，完美保留原树的“祖先 - 后代”关系、路径拓扑。
（2）虚树必存节点
构建虚树时，必须加入的节点只有两类（缺一不可）：
一是本次查询的所有关键点 (去重)，二是这些关键点两两之间的最近公共祖先 (LCA)。
（3）虚树的核心性质
虚树的节点数 ≤2k，边数 ≤2k，规模极小；
虚树的边对应原树的一条完整路径，而非原树的单条边；
虚树的根节点和原树根节点一致；
虚树是临时结构，每组查询都要重新构建，用完清空即可。
● 快读：https://blog.csdn.net/hnjzsyjyj/article/details/120131534
int read() { //fast read int x=0,f=1; char c=getchar(); while(c<'0' || c>'9') { //!isdigit(c) if(c=='-') f=-1; c=getchar(); } while(c>='0' && c<='9') { //isdigit(c) x=x*10+c-'0'; c=getchar(); } return x*f; }● 链式前向星：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
void add(int a,int b,int w) { val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++; }大佬 yxc 指出“链式前向星”就是“多单链表”，每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中：
e[idx]：存储序号为 idx 的边的终点值
ne[idx]：存储序号为 idx 的边指向的边的序号（模拟链表指针）
h[a]：存储头结点 a 指向的边的序号
val[idx]：存储序号为 idx 的边的权值（可选）
【算法代码】
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e6+5; const int LOG=20; LL val[N],e[N],ne[N],h[N],idx; int stk[N],top; int timestamp; int dfn[N],f[N][LOG+5],a[N],dep[N]; LL ans[N],dp[N]; bool flag[N]; inline int read() { //fast read int x=0,f=1; char c=getchar(); while(c<'0' || c>'9') { //!isdigit(c) if(c=='-') f=-1; c=getchar(); } while(c>='0' && c<='9') { //isdigit(c) x=x*10+c-'0'; c=getchar(); } return x*f; } inline void add(int a,int b,int w) { val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } inline bool cmp(int x,int y) { return dfn[x]<dfn[y]; } inline void dfs1(int u) { dfn[u]=++timestamp; dep[u]=dep[f[u][0]]+1; for(int i=0; i<=LOG; i++) { if(f[u][i]) f[u][i+1]=f[f[u][i]][i]; else f[u][i+1]=0; } for(int i=h[u]; i!=-1; i=ne[i]) { int j=e[i]; if(!dfn[j]) { f[j][0]=u; dp[j]=min(dp[u],val[i]); dfs1(j); } } h[u]=-1; } inline void dfs2(int u) { LL sum=0; ans[u]=dp[u]; for(int i=h[u]; i!=-1; i=ne[i]) { int j=e[i]; dfs2(j); sum+=ans[j]; } if(sum && !flag[u]) ans[u]=min(ans[u],sum); h[u]=-1; } inline int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=LOG; i>=0; i--) { if(dep[f[x][i]]>=dep[y]) x=f[x][i]; } if(x==y) return x; for(int i=LOG; i>=0; i--) { if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; } return f[x][0]; } inline void solve() { top=idx=0; int m=read(); for(int i=1; i<=m; i++) { a[i]=read(); flag[a[i]]=1; } sort(a+1,a+m+1,cmp); for(int i=1; i<=m; i++) { if(!top) { stk[++top]=a[i]; continue; } int lca=LCA(a[i],stk[top]); while(dfn[lca]<dfn[stk[top]]) { if(dfn[lca]>=dfn[stk[top-1]]) { add(lca,stk[top],0); if(stk[--top]!=lca) stk[++top]=lca; break; } add(stk[top-1],stk[top],0); top--; } stk[++top]=a[i]; } while(top>1) { add(stk[top-1],stk[top],0); top--; } dfs2(stk[1]); printf("%lld\n",ans[stk[1]]); for(int i=1; i<=m; i++) flag[a[i]]=0; } int main() { memset(h, -1, sizeof(h)); int n=read(); for(int i=1; i<n; i++) { int x=read(),y=read(),z=read(); add(x,y,z); add(y,x,z); } dp[1]=LLONG_MAX; dfs1(1); int T=read(); while(T--) { solve(); } return 0; } /* in: 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 out: 12 32 22 */
【参考文献】
https://www.cnblogs.com/zhenghaotian/p/8243410.html
https://blog.csdn.net/weixin_30539625/article/details/99542716
https://www.luogu.com.cn/problem/solution/P2495
https://www.luogu.com.cn/problem/P4103
https://www.luogu.com.cn/problem/P5680
https://www.cnblogs.com/bztMinamoto/p/10554721.html
