目录
知识点概要知识点详解ｃｏｄｅ
知识点概要
虚树在竞赛中出现的次数并不多，但其思想确实十分高妙的。对于一棵树以及对于只涉及树中一些关键点的询问，我们只需利用这些关键点及关键点之间的\(LCA\)即可求出解。这便是虚树的高妙之处，可以将复杂度优化到\(O(n*q)\)\((q\)为询问次数\()\)级别。并且有些时候我们并不需要建出这棵虚树，因为我们可以通过记录\(Dfs\)时的信息来得到这整棵树有用的信息。下面是\(luogu\)上某位\(dalao\)的高妙发言:
dfs原理 不知道大家发现一件事了没有，我们关于"树"的所有信息，绝大部分是通过dfs处理出来的，但是我们发现一件事，dfs其实在底层实现上，并不是大家脑海中想象的dfs。 当你的程序编译出来之后，你觉得你在跑dfs，但是计算机并不这么想，因为你甚至没有建树，实际上只有邻接表而已，树？不存在的，而你以为你在这个树上进行了所谓的"深度优先搜索"，而计算机并不这么认为，它只是按一定的指令对一个栈进行了反复的push和pop，期间做一些事罢了(应该都知道递归函数的实现过程隐性的开了一个栈吧……) 水了这么多，其实只是想说两件事，第一，我们做dfs可以了解树的信息，而且了解的很充分，第二，我们可以在不建树的情况下做dfs，只要我们掌握了可以模拟dfs的信息即可，也就是说，在跑dfs的过程中，我们究竟对开出来的栈进行了什么操作
知识点详解
裸着讲虚树实际上确实比较的玄，接下来我们都以\(Bzoj2286\)为例题来讲。 考虑朴素的\(Dp\)，我们假设没有多组询问，只处理一组询问是，我们可以怎么做？应该比较简单的可以想到树形\(Dp\)。对于每个点，我们记\(f[i]\)表示从\(i\)这个点到1，边的最小权值。然后我们可以列出\(Dp\)方程：\(dp[i]=min(f[i],\sum dp[j])\)(\(j\)为\(i\)的儿子)。这样对于每一组的询问，复杂度为\(O(n)\)，总复杂度为\(O(n*m)\)。 然后我们观察一下这个转移方程之后，发现对于某些点的\(Dp\)转移实际上并没有什么作用，并且题目中说了\(\sum k \leq 500000\)，通过这些信息，我们就可以考虑我们是否可以怼掉一些点，然后只通过选中的点进行\(Dp\)并取得同样的\(Dp\)结果，并且尽量最小化找到点的数量。这样，虚树的想法就应运而生了。 实际上，对于题目中的所给出的关键点，我们只需要知道这些点以及他们相互之间的\(LCA\)即可得到正确的答案了，而其他的点和边就可以压缩起来，然后我们就可以减少复杂度接近\(O(\sum k)\)级别的了。 但是我们又该如何求出两两关键点的\(LCA\)呢？显然朴素的算法是不行的，然后我们就可以想到利用\(Dfs\)序了。首先我们将所有的关键点都拿出来，然后丢进一个栈中，每次新加进一个点的时候，就进行如下判断（\(top\)表示栈顶元素，\(top-1\)表示栈中第二个元素，\(p\)表示新加进的点，\(Lca\)表示\(top\)和\(p\)的\(LCA\)）： 1.如果\(Lca=top\)，那么说明新加进来的点与栈顶元素还是在同一颗子树中，就可以直接把这个节点加入这个栈中。 2.如果\(Lca\neq top\)，则说明新加进的节点与栈顶元素已经不再同一棵子树中了，并且由于我们已经按照了\(dfn\)进行排序过了，所以这也说明了以\(Lca\)为根的子树已经遍历完毕了，现在开始我们需要重建所有在\(Lca\)节点一下的点之间的连边。为什么只要处理\(Lca\)以下的呢？还是因为我们之前按照\(dfn\)进行排序过了，所以当\(p\)与\(top\)不在一棵子树内的时候，就可以确定已经没有任意两个点的\(LCA\)在当前的\(Lca\)之下了。所以我们就需要对以\(Lca\)为根的子树进行连边了。然而连边又有许多需要分类套路的地方： 1.\(dfn[top-1]>dfn[Lca]\)时，说明这个时候\(top-1\)仍然还在\(Lca\)下面，那么我们直接在\(top-1\)与\(top\)之间连一条边，然后弹出栈顶元素就行了。 2.\(dfn[top-1]=dfn[Lca]\)时，说明这个时候\(top-1\)就是\(Lca\)了，那么还是同样的在\(top-1\)与\(top\)之间连一条边，弹出栈顶元素，然后就可以退出循环了（因为以\(Lca\)为根的子树已经处理完了）。 2.\(dfn[top-1]<dfn[Lca]\)时，说明这个时候\(top-1\)已经在\(Lca\)上面了，那么我们就可以在\(Lca\)与\(top\)之间连边，弹出栈顶元素，然后就可以退出循环了。 这样我们就可以处理出对于每一个询问只有与关键点有关的一棵虚树了。但是注意我们之前说的，我们实际上并不需要把这棵树建出来而得到这棵树中的信息，所以秉持着极简主义的我们就可以直接在构建虚树的时候就完成这个\(Dp\)了。至于正确性，管他我们可以发现每一个点在出栈之后就不会再进栈了，说明这个点在出栈的时候已经完成了所有的连边，那么实际上我们就可以直接进行\(Dp\)转移了。最后只需要预处理一下每个点到根路径上的最小权值即可。 虽然虚树理解比较难，代码量也比较长，但是掌握了之后就会觉得比较简单了，实际上就可以看作把一棵树压缩起来，注意处理好点与点之间的关系大致就没有问题了。
ｃｏｄｅ
#pragma GCC optimize (3)
#pragma GCC optimize ("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=300000;
const int M=500005;
const ll inf=0x7f7f7f7f7f7f;
struct edge {
int to,nxt,c;
}E[M];
int n,m,tot,dfnclck,q,top;
int head[maxn],dfn[maxn],p[maxn][22],deep[maxn],minn[maxn][22];
int k[maxn],isk[maxn];
ll f[maxn];
int st[maxn];
/*==================Define Area================*/
void Min(int &a,int b) {
if(a>b) a=b;
}
void Min(ll &a,ll b) {
if(a>b) a=b;
}
void addedge(int u,int v,int w) {
E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[tot].c=w;
E[++tot].to=u;E[tot].nxt=head[v];head[v]=tot;E[tot].c=w;
}
void dfs(int o,int fa,int dep) {
dfn[o]=++dfnclck;deep[o]=dep;p[o][0]=fa;
for(int i=head[o];~i;i=E[i].nxt) {
int to=E[i].to;
if(dfn[to]) continue;
minn[to][0]=E[i].c;
dfs(to,o,dep+1);
}
}
int Lca(int a,int b) {
if(deep[a]<deep[b]) swap(a,b);
for(int i=20;~i;i--) if(deep[p[a][i]]>=deep[b]) a=p[a][i];
for(int i=20;~i;i--) if(p[a][i]!=p[b][i]) a=p[a][i],b=p[b][i];
return a==b ? a : p[a][0];
}
ll Getmin(int a,int b) {
ll ans=inf;
for(int i=20;~i;i--) {
if(deep[p[a][i]]>=deep[b]) {
Min(ans,minn[a][i]);
a=p[a][i];
}
}
return ans;
}
bool cmp(int a,int b) {
return dfn[a]<dfn[b];
}
void Solve() {
st[++top]=1;
sort(k+1,k+1+q,cmp);
for(int i=1;i<=q;i++) isk[k[i]]=1;
for(int i=1;i<=q;i++) {
int o=k[i];
int L=Lca(o,st[top]);
while(deep[L]<deep[st[top]]) {
if(deep[st[top-1]]<=deep[L]) {
f[L]+=min(isk[st[top]] ? inf : f[st[top]],Getmin(st[top],L));
f[st[top]]=isk[st[top]]=0;
top--;
if(st[top]!=L) st[++top]=L;
break;
}
else {
f[st[top-1]]+=min(isk[st[top]] ? inf : f[st[top]],Getmin(st[top],st[top-1]));
f[st[top]]=isk[st[top]]=0;
top--;
}
}
if(st[top]!=o) st[++top]=o;
}
while(top>1) {
f[st[top-1]]+=min(isk[st[top]] ? inf : f[st[top]],Getmin(st[top],st[top-1]));
f[st[top]]=isk[st[top]]=0;
top--;
}
printf("%lld\n",f[top--]);
f[1]=0;
}
void Init() {
dfs(1,0,1);
for(int i=1;i<=20;i++) {
for(int j=1;j<=n;j++) {
p[j][i]=p[p[j][i-1]][i-1];
minn[j][i]=min(minn[j][i-1],minn[p[j][i-1]][i-1]);
}
}
}
signed main() {
// freopen("1.in","r",stdin);
// freopen("3.out","w",stdout);
memset(minn,0x3f,sizeof minn);
memset(head,-1,sizeof head);
read(n);
for(int i=1;i<n;i++) {
int u,v,w;
read(u);read(v);read(w);
addedge(u,v,w);
}
Init();
read(m);
for(int i=1;i<=m;i++) {
read(q);
for(int i=1;i<=q;i++) {
read(k[i]);
}
Solve();
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9475371.html
