虚树（板子整理+知识总结）

思路来源

https://www.cnblogs.com/stoorz/p/12388534.html 板子

https://www.cnblogs.com/zwfymqz/p/9175152.html 构建过程、复杂度证明

知识点整理

以下部分来自https://www.cnblogs.com/zwfymqz/p/9175152.html

维护一个栈，建虚树的时候分三种情况，一边dfs一边建即可

一般考察虚树dp，复杂度是O(2*sumk)，因为加入一个点最多多一个lca

板子整理

把0号点当做一个默认出现的虚点，这样统一了很多情况

key[i]=1的点是虚树标记的点，par关系是新建的虚树

#include<bits/stdc++.h> using namespace std; const int N=200010,LG=20; int n,m; vector<int>e[N] int stk[N],top;//虚树栈 int dep[N],f[N][LG+1];//lca int par[N];//虚树 bool key[N];//关键点 int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=LG;i>=0;i--){ if(dep[f[x][i]]>=dep[y]){ x=f[x][i]; } } if(x==y)return x; for(int i=LG;i>=0;i--){ if(f[x][i]!=f[y][i]){ x=f[x][i],y=f[y][i]; } } return f[x][0]; } void dfs(int u,int fa){ dep[u]=dep[fa]+1; f[u][0]=fa; for(int i=1;i<=LG;i++){ f[u][i]=f[f[u][i-1]][i-1]; } if(key[u]){ int p=lca(u,stk[top]); if(p!=stk[top]){ while(dep[stk[top-1]]>dep[p]){ par[stk[top]]=stk[top-1]; top--; } par[stk[top]]=p; top--; if(stk[top]!=p){ stk[++top]=p; } } stk[++top]=u; } for(int v:e[u]){ if(v==fa)continue; dfs(v,u); } } void build(){//以0为虚根 top=1; dfs(1,0); for(int i=top;i>=1;i--){ par[stk[i]]=stk[i-1]; } } int main(){ return 0; }