本文共 10225 字，大约阅读时间需要 34 分钟。

之前的之前

之前的之前，可以做做这题，领略虚树的思想

学习之前的例题

在学虚树之前，先来看一道题：

大致题意是这样的，现在有n个点，n-1条带权边的树，有m个询问，每个询问，给出k个点，（其中不包含1号节点），要删除一些边使得1号点与给出的点不连通，求删除边和的最小值。

乍一看，是不是觉得显然是树形dp呢，而且树形dp还是$\Theta (n)$的，十分优越

但是，不幸的是，$2\le n\le 250000$的情况下，$1\le m\le 500000$，如果是$\Theta (nm)$显然会TLE，但是又有一个好消息$\Sigma k_i\le 500000$。

那么考虑一下怎么做，可能有些难想，这个时候就该引入虚树啦，此题可以用虚树解决

虚树的概念

虚树，就是在有一棵树的情况下，对于数量较少的点进行询问时所建的一棵新的树，虚树包含询问的点和询问的点的lca（最近公共祖先），上面的点被称为关键点。对于两个关键点A，B，它们的连边上包含着原本树上两点之间那条链上的关键信息（这个信息可以是边权最大值、边权最小值、或者是边权之和，这个取决于实际需要），然后就可以进行树形dp了，这样的复杂度是基于询问的点数的，就可以想象虚树就是把一棵大树浓缩成一棵拥有所有你需要的信息的小树。

建树的方法

那么怎么建树呢，比较常见的做法是维护一个栈，里面存储着一条链，每一次加入一个点进行操作。

具体列举一下步骤吧

预备知识：

用较优的复杂度求lca，以及求两点之间的距离，一般倍增做，或者树链剖分加前缀和都可以，这都是单次$\Theta (logn)$的，另外呢，要事先求好原树的dfs序和每个点的深度（这里的深度是指点序的深度，在计算这个深度的时候每条边都是为1来算），后面要用

询问操作：

1.输入每个询问的点，并且按照dfs序为关键字排序

2.将第1个点压到栈当中，开始构建虚树 3.枚举到下一个点u，计算u与栈顶点v的公共祖先lca 4.假设栈中栈顶下方的点为w（若栈中只有1个点就直跳过这一步），若w点的深度大于lca就把v向w连一条边，并且弹掉v，重复此步，否则就到下一步 5.若lca不是当前的v，那么就把lca和v连边，把v弹出，让lca成为栈顶元素（注：这个操作的意思是如果栈顶没有这个lca那么就压入），否则不做任何操作 6.最后把u压入栈中 7.回到3操作枚举下个点，直到枚举完了所有点 8.把栈顶v与栈顶下方的点为w连边，并且把v弹掉，这么做直到栈里只有一个点 9.栈里剩下的点就是虚树的根了 接下来你就可以开始进行dp等操作了

虚树的复杂度

虚树的建树的复杂度是$\Theta (klogn)$的，树形dp就是$\Theta (k)$的啦，因为考虑最后虚树上的关键点有询问的点，和lca，然后每个询问的点最多产生1个新的lca，所以复杂度就是对的啦

有关虚树用建树的几点技巧

首先栈里面最后剩下的点就是虚树的根节点，这个很好用

然后对于很多题目建虚树都要建多次，那么 邻接表/vector 的同学都要清空 head/vector ，如果 memset/一个个枚举clear 那肯定会T的，我往往都会在树形dp时用完边后进行清空，就非常高效了

开头的题的题解

对于这一题把1号点作为根，对于每个询问都建一棵虚树，然后进行树形dp，这一题当中可以发现若一个点是另一个点的祖先，那么只需保留深度小的那个点，那么建好的虚树中只有叶子节点是需要被截断的，树形dp可以用f[i][0]表示截断i点的子节点的最小代价，f[i][1]表示不截断的最小代价（当然可以少一维，但是为了方便我就这么定义啦）

下面是代码

#include
   
    #include
    
     namespace fast_IO{
       const int IN_LEN=10000000,OUT_LEN=10000000;    char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;    inline char getchar_(){
   return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}    inline void putchar_(const char x){
   if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}    inline void flush(){
   fwrite(obuf,1,oh-obuf,stdout);}}using namespace fast_IO;#define getchar() getchar_()#define putchar(x) putchar_((x))typedef long long LL;#define rg registertemplate 
     
       inline T max(const T a,const T b){
   return a>b?a:b;}template 
      
        inline T min(const T a,const T b){
   return a
       
        
          inline T abs(const T a){ return a>0?a:-a;}template 
         
           inline void swap(T&a,T&b){ T c=a;a=b;b=c;}template 
          
            inline T gcd(const T a,const T b){ if(a%b==0)return b;return gcd(b,a%b);}template 
           
             inline T square(const T x){ return x*x;};template 
            
              inline void read(T&x){ char cu=getchar();x=0;bool fla=0; while(!isdigit(cu)){ if(cu=='-')fla=1;cu=getchar();} while(isdigit(cu))x=x*10+cu-'0',cu=getchar(); if(fla)x=-x; }template 
             
               void printe(const T x){ if(x>=10)printe(x/10); putchar(x%10+'0');}template 
              
                inline void print(const T x){ if(x<0)putchar('-'),printe(-x); else printe(x);}inline void judge(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout);}#include
               
                #include
                
                 const int maxn=250001,maxm=500001;int bit[19];int n,m,s;int head[maxn],nxt[maxm],tow[maxm],vau[maxm],tmp=1;int who[maxn][19],dis[maxn][19];int dep[maxn];inline void addb(const int u,const int v,const int w){ tmp++; nxt[tmp]=head[u]; head[u]=tmp; tow[tmp]=v; vau[tmp]=w;}int tid[maxn],tim;inline void dfs(const int u){ tid[u]=++tim; for(rg int i=head[u];i;i=nxt[i]) { const int v=tow[i]; if(who[u][0]!=v) { who[v][0]=u; dis[v][0]=vau[i]; dep[v]=dep[u]+1; dfs(v); } }}inline int lca(int a,int b){ if(dep[a]
                 
                  =0;i--) if(who[a][i]!=who[b][i]) a=who[a][i],b=who[b][i]; return who[a][0];}inline int dist(int a,int b){ rg int ans=0x7fffffff; if(dep[a]
                  
                   =0;i--) if(who[a][i]!=who[b][i]) ans=min(ans,min(dis[a][i],dis[b][i])),a=who[a][i],b=who[b][i]; return min(ans,min(dis[a][0],dis[b][0]));}int head_[maxn],nxt_[maxm],tow_[maxm],vau_[maxm],tmp_;inline void addb_(const int u,const int v,const int w){ tmp_++; nxt_[tmp_]=head_[u]; head_[u]=tmp_; tow_[tmp_]=v; vau_[tmp_]=w;}int k,h[maxn];bool cmp(const int x,const int y){ return tid[x]
                   
                    1&&dep[stack[top-1]]>dep[LCA]) { const int DIS=dist(stack[top-1],stack[top]); addb_(stack[top-1],stack[top],DIS),addb_(stack[top],stack[top-1],DIS); top--; } if(dep[stack[top]]>dep[LCA]) { const int DIS=dist(LCA,stack[top]); addb_(LCA,stack[top],DIS),addb_(stack[top],LCA,DIS); top--; } if(!top||dep[stack[top]]
                    
                     1) { const int DIS=dist(stack[top-1],stack[top]); addb_(stack[top-1],stack[top],DIS),addb_(stack[top],stack[top-1],DIS); top--; } dfs(1,0); print(dp[1][0]); putchar('\n'); } return 0;}
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

再来一题

由于前面那题有一些特殊性质，代码可能不能作为虚树的模板，所以呢，现在再引入一道题

简要题意就是现在有一棵n个点，n-1条边的树，给出q个询问，每次询问给出mi个重要点，树上的每一个点都属于离其最近的重要点，若有多个点满足条件，那么它属于这其中编号最小的点，对于每个询问中需要输出每个给出的重要点所管辖点的数量。n<=300000,q<=300000,m[1]+m[2]+…+m[q]<=300000 怎么做，很显然还是通过建虚树然后进行树形dp啦，这道题其实有些麻烦，后面的树形dp贼烦（为了便于理解，我dfs了多遍，导致代码量大大增加），对于每条虚树边都可能属于一个点或者被瓜分成两份，对于虚树上的非关键点，首先计算它属于哪个点，然后算出它的出边的树中不属于自己所在重要点的点的数量（除了朝向自己属于的重要点的方向，这个可以通过和重要点的距离来判），然后对于每一个重要点所管辖点的数量是n-不属于自己的点的数量就好了。解释可能不是很清楚，下面贴出代码（update:由于写此份代码的时候太菜，思路不够清晰，所以当时为了方便思考导致树形dp这一部分写的很长，实际树形dp的清真实现可以去参考网上的其它代码）：

#include
   
    #include
    
     #include
     
      #include
      
        namespace fast_IO{
       const int IN_LEN=10000000,OUT_LEN=10000000;    char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;    inline char getchar_(){
   return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}    inline void putchar_(const char x){
   if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}    inline void flush(){
   fwrite(obuf,1,oh-obuf,stdout);}}using namespace fast_IO;#define getchar() getchar_()#define putchar(x) putchar_((x))#define rg registertypedef long long LL;template 
       
         inline T max(const T a,const T b){
   return a>b?a:b;}template 
        
          inline T min(const T a,const T b){ return a
         
          
            inline void mind(T&a,const T b){ a=a
           
            
              inline void maxd(T&a,const T b){ a=a>b?a:b;}template 
             
               inline T abs(const T a){ return a>0?a:-a;}template 
              
                inline void swap(T&a,T&b){ T c=a;a=b;b=c;}template 
               
                 inline T gcd(const T a,const T b){ if(!b)return a;return gcd(b,a%b);}template 
                
                  inline T lcm(const T a,const T b){ return a/gcd(a,b)*b;}template 
                 
                   inline T square(const T x){ return x*x;};template 
                  
                    inline void read(T&x){ char cu=getchar();x=0;bool fla=0; while(!isdigit(cu)){ if(cu=='-')fla=1;cu=getchar();} while(isdigit(cu))x=x*10+cu-'0',cu=getchar(); if(fla)x=-x;}template 
                   
                     inline void printe(const T x){ if(x>=10)printe(x/10); putchar(x%10+'0');}template 
                    
                      inline void print(const T x){ if(x<0)putchar('-'),printe(-x); else printe(x);}const int maxn=300001,maxm=600001;int bit[19];int n,m,s;int head[maxn],nxt[maxm],tow[maxm],tmp=1;int who[maxn][19],dis[maxn][19];int dep[maxn];inline void addb(const int u,const int v){ tmp++; nxt[tmp]=head[u]; head[u]=tmp; tow[tmp]=v;}int tid[maxn],tim,size[maxn];inline void dfs(const int u){ tid[u]=++tim,size[u]=1; for(rg int i=head[u];i;i=nxt[i]) { const int v=tow[i]; if(who[u][0]!=v) { who[v][0]=u; dis[v][0]=1; dep[v]=dep[u]+1; dfs(v); size[u]+=size[v]; } }}inline int lca(int a,int b){ if(dep[a]
                     
                      =0;i--) if(who[a][i]!=who[b][i]) a=who[a][i],b=who[b][i]; return who[a][0];}inline int dist(int a,int b){ rg int ans=0; if(dep[a]
                      
                       =0;i--) if(who[a][i]!=who[b][i]) ans+=dis[a][i]+dis[b][i],a=who[a][i],b=who[b][i]; return ans+dis[a][0]+dis[b][0];}int head_[maxn],nxt_[maxm],tow_[maxm],vau_[maxm],tmp_;inline void addb_(const int u,const int v,const int w){ tmp_++; nxt_[tmp_]=head_[u]; head_[u]=tmp_; tow_[tmp_]=v; vau_[tmp_]=w;}int k,h[maxn],ans[maxn],belo[maxn],Dis[maxn];int qu[maxn];bool sign[maxn];bool cmp(const int x,const int y){ return tid[x]
                       
                        Dis[v]||v==belo[u])continue; rg int p; if(v!=fa)dfs2(v,u); if(belo[v]==belo[u])ans[u]+=ans[v]; else if(sign[v]) { if(v!=fa) { if((Dis[u]+vau_[i])&1)p=check(v,(Dis[u]+vau_[i])/2); else if(v
                        
                         belo[u])p=check(u,(Dis[u]+vau_[i])/2-Dis[u]); else p=check(u,(Dis[u]+vau_[i])/2-Dis[u]-1); ans[u]+=n-size[p]; } } else { if(v!=fa) { if((Dis[u]+Dis[v]+vau_[i])&1)p=check(v,(Dis[u]+Dis[v]+vau_[i])/2-Dis[v]); else if(belo[v]
                         
                          belo[u])p=check(u,(Dis[u]+Dis[v]+vau_[i])/2-Dis[u]); else p=check(u,(Dis[u]+Dis[v]+vau_[i])/2-Dis[u]-1); ans[u]+=n-size[p]; } } } for(rg int i=head_[u];i;i=nxt_[i]) { const int v=tow_[i]; if(belo[v]==belo[u]&&Dis[u]>Dis[v]||v==belo[u]) if(v!=fa) dfs2(v,u); } }}void dfs3(const int u,const int fa){ if(sign[u]) { ans[u]=n; for(rg int i=head_[u];i;i=nxt_[i]) { const int v=tow_[i]; rg int p; if(v!=fa)dfs3(v,u); if(belo[v]==u)ans[u]-=ans[v]; else if(sign[v]) { if(v!=fa) { if(vau_[i]&1)p=check(v,vau_[i]/2); else if(v
                          
                           u)p=check(u,vau_[i]/2); else p=check(u,vau_[i]/2-1); ans[u]-=n-size[p]; } } else { if(v!=fa) { if((Dis[v]+vau_[i])&1)p=check(v,(Dis[v]+vau_[i])/2-Dis[v]); else if(u
                           
                            belo[v])p=check(u,(Dis[v]+vau_[i])/2-1); else p=check(u,(Dis[v]+vau_[i])/2); ans[u]-=n-size[p]; } } } } else { for(rg int i=head_[u];i;i=nxt_[i]) { const int v=tow_[i]; if(v!=fa)dfs3(v,u); } }}void dfs4(const int u,const int fa){ if(sign[u]) { for(rg int i=head_[u];i;i=nxt_[i]) { const int v=tow_[i]; if(v!=fa)dfs4(v,u); } sign[u]=0; } else { for(rg int i=head_[u];i;i=nxt_[i]) { const int v=tow_[i]; if(v!=fa)dfs4(v,u); } belo[u]=0; } head_[u]=0,Dis[u]=0x7f7f7f7f;}int main(){ memset(Dis,0x7f,sizeof(Dis)); bit[0]=1; for(rg int i=1;i<=18;i++)bit[i]=bit[i-1]<<1; read(n),s=1; for(rg int i=1;i
                            
                             1&&dep[stack[top-1]]>dep[LCA]) { const int DIS=dist(stack[top-1],stack[top]); addb_(stack[top-1],stack[top],DIS),addb_(stack[top],stack[top-1],DIS); top--; } if(dep[stack[top]]>dep[LCA]) { const int DIS=dist(LCA,stack[top]); addb_(LCA,stack[top],DIS),addb_(stack[top],LCA,DIS); top--; } if(!top||dep[stack[top]]
                             
                              1) { const int DIS=dist(stack[top-1],stack[top]); addb_(stack[top-1],stack[top],DIS),addb_(stack[top],stack[top-1],DIS); top--; } dfs1_0(stack[1],0); dfs1_1(stack[1],0); dfs2(stack[1],0); dfs3(stack[1],0); dfs4(stack[1],0); for(rg int i=1;i<=k;i++)print(ans[qu[i]]),putchar(' '); putchar('\n'); } return flush(),0;}
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

总结

上面两道例题差不多覆盖了差不多虚树要用到的所以基础操作了，总结一个虚树的板子还是挺好的，虚树写起来简单，也挺好用的，复杂度也挺优秀，值得好好研究一番

update by 2018.3:感谢Michael_Li对本篇博客的建议与指正 update by 2019.1:对部分公式进行了美化更新

转载地址：https://blog.csdn.net/zhouyuheng2003/article/details/79110326 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！