虚树 Virtual Tree
浓缩信息，把一整颗大树浓缩成一颗小树。
下图中，红色结点是我们选择的关键点。红色和黑色结点都是虚树中的点。黑色的边是虚树中的边。
OIWIKI
两种建树方式
1.第一种构造过程：二次排序 + LCA 连边(容易理解，常数略大)
bool cmp(int x, int y) {
return dfn[x] < dfn[y]; // 按照 dfn 序排序
}
void build()
{
sort(h+1,h+1+m,cmp);//按dfn序从小到大
for(int i=1;i<m;i++)
{
a[++len]=h[i];
a[++len]=lca(h[i],h[i+1]);
}
a[++len]=h[m];
sort(a+1,a+1+len,cmp);
len=unique(a+1,a+1+len)-a-1;
for(int i=1,lc;i<len;i++)
{
lc=lca(a[i],a[i+1]);
connect(lc,a[i+1]);
}
}
2.第二种:单调栈
链式前向星魅力时刻：其中有很多细节，比如用邻接表存图的方式存虚树的话，需要清空邻接表。但是直接清空整个邻接表是很慢的，所以我们在 有一个从未入栈的元素入栈的时候清空该元素对应的邻接表 即可。
void build(int M)
{
sort(ls+1,ls+1+M,cmp);//按dfn序从小到大
sta[top=1]=1;head[1]=0;cnt=0;// 1 号节点入栈，清空 1 号节点对应的邻接表，设置邻接表边数为 1
for(int i=1;i<=M;i++)
{
if(ls[i]!=1)
{
int l=lca(ls[i],sta[top]);
if(l!=sta[top])
{
while(dfn[l]<dfn[sta[top-1]])
add(sta[top-1],sta[top]),top--;
if(dfn[l]>dfn[sta[top-1]]) // 如果 LCA 不等于次大节点（这里的大于其实和不等于没有区别）
head[l]=0,add(l,sta[top]),sta[top]=l; // 说明 LCA 是第一次入栈，清空其邻接表，连边后弹出栈顶元素，并将 LCA// 入栈
else add(l,sta[top--]); // 说明 LCA 就是次大节点，直接弹出栈顶元素
}
head[ls[i]]=0;sta[++top]=ls[i];
}
}
for(int i=1;i<top;i++)add(sta[i],sta[i+1]);
}
P2495 [SDOI2011] 消耗战
我们发现如果每一次都跑一遍\(O(n)\)\(DP\)是不值当的，所以可以建虚树
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pb push_back
using namespace std;
const int N = 2.5e5+5;
vector <pair<int,int>> e[N];
struct eg
{
int u,v,w,next;
}edge[N<<1];int cnt,head[N];
void add(int u,int v)
{
edge[++cnt].u=u;
edge[cnt].v=v;
edge[cnt].next=head[u];head[u]=cnt;
}
int n,m,f[N][25],dfn[N],rk[N],dfstot,dep[N];ll minv[N];
void dfs(int u)
{
dfn[u]=++dfstot;rk[dfstot]=u;
dep[u]=dep[f[u][0]]+1;
for(int i=1;i<=20;i++)
f[u][i]=f[f[u][i-1]][i-1];
for(auto [to,w]:e[u])
{
if(to==f[u][0])continue;
minv[to]=min<ll>(minv[u],w);
f[to][0]=u;
dfs(to);
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)
if(dep[f[u][i]]>=dep[v])u=f[u][i];
if(u==v)return u;
for(int i=20;i>=0;i--)
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
return f[u][0];
}
int ls[N],query[N],sta[N],top;
bool cmp(int a,int b){return dfn[a]<dfn[b];};
void build(int M)
{
sort(ls+1,ls+1+M,cmp);//按dfn序从小到大
sta[top=1]=1;head[1]=0;cnt=0;// 1 号节点入栈，清空 1 号节点对应的邻接表，设置邻接表边数为 1
for(int i=1;i<=M;i++)
{
if(ls[i]!=1)
{
int l=lca(ls[i],sta[top]);
if(l!=sta[top])
{
while(dfn[l]<dfn[sta[top-1]])
add(sta[top-1],sta[top]),top--;
if(dfn[l]>dfn[sta[top-1]]) // 如果 LCA 不等于次大节点（这里的大于其实和不等于没有区别）
head[l]=0,add(l,sta[top]),sta[top]=l; // 说明 LCA 是第一次入栈，清空其邻接表，连边后弹出栈顶元素，并将 LCA// 入栈
else add(l,sta[top--]); // 说明 LCA 就是次大节点，直接弹出栈顶元素
}
head[ls[i]]=0;sta[++top]=ls[i];
}
}
for(int i=1;i<top;i++)add(sta[i],sta[i+1]);
}
ll dfs1(int u)
{
ll sum=0;ll tem;
for(int i=head[u];i;i=edge[i].next)
{
int to=edge[i].v;
sum+=dfs1(to);
}
if(query[u])
tem=minv[u];
else
tem=min(minv[u],sum);
query[u]=0;
head[u]=0;
return tem;
}
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n;int u,v,w;
for(int i=1;i<=n-1;i++)
{
cin>>u>>v>>w;
e[u].pb({v,w});e[v].pb({u,w});
}
minv[1]=1e18;
dfs(1);
cin>>m;
int num;
while(m--)
{
cin>>num;
for(int i=1;i<=num;i++)
{
cin>>ls[i];query[ls[i]]=1;
}
// num++
// sort(ls+1,ls+1+num,cmp);
// cout<<m<<endl;
build(num);
cout<<dfs1(1)<<endl;
}
return 0;
}