树上算法集合
2026-08-18 20:21:27
发布于：广东
25阅读
0回复
0点赞
啊喵喵喵树比图要多一些机制,
所!以!
我要新发一篇帖子~
Tarjan算法
这里要讲一下,这并不是主流求LCA的算法,是不太好理解但空间时间都非常good还很短(不是重点)的算法
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void tarjan(int u){
vis[u]=true;//为这个点标记,若有标记说明已经被并入父亲的集合,可以求解
for(int v:g[u]){//递归所有子树
if(vis[v]) continue;
tarjan(v);
fa[v]=u;
}
for(auto p:q[u]){//处理每个询问,将询问按邻接表+pair的方式存储两个要求的数和问题编号,后续按照编号输出
int v=p.first,id=p.second;
if(vis[v]) ans[id]=find(v);//利用并查集的find
}
}
倍增法解决LCA
这个是我们常用的方法,没Tarjan好用(个人认为),放后面展示
//最开始要初始化depth[s]=1;
void dfs(int u,int f){
fa[u][0]=f;
for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:g[u]){
if(v==f) continue;
depth[v]=depth[u]+1;
dfs(v,u);
}
}
int LCA(int x,int y){
if(depth[x]<depth[y]) swap(x,y);
for(int i=20;i>=0;i--){
if(depth[fa[x][i]]>=depth[y]) x=fa[x][i];
}
if(x==y) return x;
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
树上常见操作探索
void dfs(int u,int fa){
size[u]=1;//子树大小
for(int v:g[u]){
if(v==fa) continue;
depth[v]=depth[u]+1;//深度
dfs(v,u);
size[u]+=size[v];
}
}
最!后!
我要喵两句,递归栈的内存分配和时间复杂度差不多,没超时大胆递归,别信AI说的会栈上溢的鬼话
(某苦喵曾手搓结构体栈模拟递归WA了不知道多少次)
有帮助，赞一个