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

思路来源

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
using namespace std;
const int N=200010,LG=20;
int n,m;
vectore[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]=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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！