首页 > 其他分享 >DFS求LCA

DFS求LCA

时间:2024-01-15 09:01:58浏览次数:43  
标签:结点 int mi DFS dfn LCA

  • Update on 2023.7.17:该技巧目前已知的最早来源:skip2004
  • Update on 2023.7.17:比较时,取时间戳较小的结点也是正确的,不用记录深度。

DFS 序求 LCA 无论是从时间常数,空间常数还是好写程度方面均吊打欧拉序。

定义

DFS 序表示对一棵树进行深度优先搜索得到的 结点序列,而 时间戳 DFN 表示每个结点在 DFS 序中的位置。这两个概念需要着重区分。

算法介绍

考虑树上的两个结点 u,v 及其最近公共祖先 d,我们不得不使用欧拉序求 LCA 的原因是在欧拉序中,du,v 之间出现过,但在 DFS 序中,d 并没有在 u,v 之间出现过。对于 DFS 序而言,祖先一定出现在后代之前(性质)。

不妨设 u 的 DFN 小于 v 的 DFN(假设)。

u 不是 v 的祖先 时(情况 1),DFS 的顺序为从 d 下降到 u,再回到 d,再往下降到 v

根据性质,任何 d 以及 d 的祖先均不会出现在 uv 的 DFS 序中。

考察 dv 方向上的第一个结点 v,即设 vd 的 / 子树包含 v 的 / 儿子。根据 DFS 的顺序,显然 vuv 的 DFS 序之间。

这意味着什么?我们只需要求在 u 的 DFS 序和 v 的 DFS 序之间深度最小的任意一个结点,那么 它的父亲 即为 u,v 的 LCA。

这样做的正确性依赖于在 DFS 序 uv 之间,d 以及 d 的祖先必然不会存在,且必然存在 d 的儿子。

u,v 成祖先后代关系(情况 2)是容易判断的,但这不优美,不能体现出 DFS 求 LCA 的优势:简洁。为了判断还要记录每个结点的子树大小,但我们自然希望求 LCA 的方法越简单越快越好。

根据假设,此时 u 一定是 v 的祖先。因此考虑令查询区间从 [dfnu,dfnv] 变成 [dfnu+1,dfnv]

对于情况 1,u 显然一定不等于 v,所以情况 2 对于算法进行的修改仍然适用于情况 1。

综上,若 uv,则 u,v 之间的 LCA 等于在 DFS 序中,位置在 dfnu+1dfnv 之间的深度最小的结点的父亲。若 u=v,则它们的 LCA 就等于 u,这是唯一需要特判的情况。

预处理 ST 表的复杂度仍为 O(nlogn),但常数减半。以下是模板题 P3379 的代码。

cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
int n, m, R, dn, dfn[N], mi[19][N];
vector<int> e[N];
int get(int x, int y) {return dfn[x] < dfn[y] ? x : y;}
void dfs(int id, int f) {
  mi[0][dfn[id] = ++dn] = f;
  for(int it : e[id]) if(it != f) dfs(it, id); 
}
int lca(int u, int v) {
  if(u == v) return u;
  if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
  int d = __lg(v - u++);
  return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}
int main() {
  scanf("%d %d %d", &n, &m, &R);
  for(int i = 2, u, v; i <= n; i++) {
    scanf("%d %d", &u, &v);
    e[u].push_back(v), e[v].push_back(u);
  }
  dfs(R, 0);
  for(int i = 1; i <= __lg(n); i++)
  for(int j = 1; j + (1 << i) - 1 <= n; j++)
    mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
  for(int i = 1, u, v; i <= m; i++) scanf("%d %d", &u, &v), printf("%d\n", lca(u, v));
  return 0;
}

和各种 LCA 算法的对比

对比 DFS 序和欧拉序,不仅预处理的时间常数砍半(欧拉序 LCA 的瓶颈恰好在于预处理,DFS 是线性),空间常数也砍半(核心优势),而且还更好写(对于一些题目就不需要再同时求欧拉序和 DFS 序了),也不需要担心忘记开两倍空间,可以说前者从各个方面吊打后者。

对比 DFS 序和倍增,前者单次查询复杂度更优。

对于 DFS 序和四毛子,前者更好写,且单次查询常数更小(其实差不多)。

对于 DFS 序和树剖,前者更好写,且单次查询复杂度更优(但树剖常数较小)。

将 DFS 序求 LCA 发扬光大,让欧拉序求 LCA 成为时代的眼泪!

标签:结点,int,mi,DFS,dfn,LCA
From: https://www.cnblogs.com/wyb-blog/p/17964609

相关文章

  • 搜索学习笔记+杂题 (基础二 dfs/bfs的拓展)
    搜索杂题:博客中讲述的题的题单:戳我二、dfs/bfs的各种变式1、深搜深搜以指数级的时间复杂度闻名,稍不注意时间就会爆炸,所以一般会用到剪枝的技巧(这个技巧基本上是因题而异,需要平时的刷题与积累)。深搜同样也是一种可变性极高的算法(其实都可以不叫做一种算法,深搜已经是一种做题的......
  • abc099d<dfs,枚举排列方案>
    题目D-GoodGrid思路用一个对角线上颜色相同,间隔3个对角线上颜色相同,一共分为3组;考虑在c种颜色中,选择3种,分配给这3组,共\(A(n,3)\)种选法;dfs枚举排列方案,对每种方案计算花费,取最优即可。总结dfs枚举排列方案;代码点击查看代码#include<iostream>#include<algor......
  • FastDFS 介绍
    一、介绍FastDFS是一个开源的轻量级分布式文件系统,它对文件进行管理,功能包括:文件存储、文件同步、文件访问(文件上传、文件下载)等,解决了大容量存储和负载均衡的问题。特别适合以文件为载体的在线服务,如相册网站、视频网站等等。FastDFS为互联网量身定制,充分考虑了冗余备份、负载......
  • adfs证书更新
    adfs更换服务通信证书1.将pfx证书安装到所有adfs服务器上,位置:证书\计算机\个人2.右击证书>所有任务>管理私钥>添加,将ADFS部署过程中添加的ADFS服账户赋权,读取权限即可查看adfs服务,可以看到所用的服务账户3.通过powershell命令设置新证书:dircert:\LocalMachine\My#获取新证书......
  • 自定义ADFS登录页
    修改adfs登录页公司名称:Set-AdfsGlobalWebContent-CompanyName"ExchangeOWA" 参考:ADFS自定义:https://learn.microsoft.com/zh-cn/windows-server/identity/ad-fs/operations/ad-fs-customization-in-windows-server#custom-themes-and-advanced-custom-themes 修改ADFS登录页......
  • Hadoop(3.3.4)-HDFS操作
    ApacheHadoop3.3.4–Overview01.appendToFilehadoopfs-appendToFilelocalfile/user/hadoop/hadoopfilehadoopfs-appendToFilelocalfile1localfile2/user/hadoop/hadoopfilehadoopfs-appendToFilelocalfilehdfs://nn.example.com/hadoop/hadoopfilehadoop......
  • Hazelcast 的事务处理与一致性保证
    1.背景介绍在现代分布式系统中,事务处理和一致性保证是非常重要的问题。Hazelcast是一个高性能的分布式计算平台,它提供了一种高效的事务处理和一致性保证机制。在这篇文章中,我们将深入探讨Hazelcast的事务处理和一致性保证机制,并分析其核心概念、算法原理、实现细节以及未来发展......
  • 深度优先搜索(DFS) 学习、Java代码实现
    深度优先搜索(DFS) 的基本思想:从图中的某个顶点v出发,然后依次从未被访问的v 的邻接点开始深度优先搜索,直至图中所有和 v 路径相通的顶点都被访问,然后选择另外一个没有被访问的顶点开始深度优先搜索。 1. 概述 深度优先搜索(DFS) 的基本思想:从图中的某个顶点v出发,然后依次......
  • Volcano 原理、源码分析(一)
    0.总结前置1.概述2.Volcano核心概念2.1认识Queue、PodGroup和VolcanoJob2.2.Queue、PodGroup和VolcanoJob的关系3.Volcano调度框架概览4.源码分析4.1Action实现在哪里?4.2从main函数入手看调度器启动过程4.2.1入口逻辑4.2.2NewScheduler()......
  • fastDFS分布式文件系统
    一、分布式文件系统的背景1.1技术应用场景当一个网站中存在大量的图片,视频,文档等文件时,往往会碰见很多问题,比如大量文件如何高效存储,用户量太大如何保证下载速度?分布式文件系统解决了海量文件存储及传输访问的瓶颈问题,对海量视频、图片的管理等。1.2文件系统文件系统是负责管理和......