首页 > 其他分享 >冷门科技 —— DFS 序求 LCA

冷门科技 —— DFS 序求 LCA

时间:2023-07-19 22:23:51浏览次数:37  
标签:结点 int 序求 DFS dfn LCA

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

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

定义

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

算法介绍

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

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

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

根据性质,任何 \(d\) 以及 \(d\) 的祖先均不会出现在 \(u\sim v\) 的 DFS 序中。

考察 \(d\) 在 \(v\) 方向上的第一个结点 \(v'\),即设 \(v'\) 为 \(d\) 的 / 子树包含 \(v\) 的 / 儿子。根据 DFS 的顺序,显然 \(v'\) 在 \(u\sim v\) 的 DFS 序之间。

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

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

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

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

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

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

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

#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,序求,DFS,dfn,LCA
From: https://www.cnblogs.com/alex-wei/p/DFN_LCA.html

相关文章

  • 小明以 hadoop 用户身份在 HDFS 上 hadoop 目录下创建 expl 目录时,发现该目
    使用Hadoop创建目录引言Hadoop是一个开源的分布式计算框架,提供了可靠性和高可扩展性的存储和处理大数据的能力。其中的分布式文件系统HDFS(HadoopDistributedFileSystem)是Hadoop的核心组件之一,用于存储和管理海量数据。在HDFS上进行目录和文件的操作是使用Hadoop命令行工具或者......
  • SaeweedFS操作
    #mdir存储元数据的数据目录#port监听端口#peers主节点ip:端口#defaultReplication备份策略#ip服务器ip#garbageThreshold清空和回收空间的阈值#maxCpu最大cpu数量,0是所有#pulseSeconds心跳检测的时间间隔单位为秒#ip.bind绑......
  • Docker安装的fastdfs基于不同服务器的数据迁移
    首先,基于docker搭建新的fastdfs中间件,参考地址为:https://blog.csdn.net/ming19951224/article/details/126933299然后将原服务器的storage文件夹下的data文件夹进行备份,打包成bak.zip 将bak.zip下载后上传到新服务器的storage文件夹下 使用unzip解压缩bak.zip,然后进入data.......
  • dfs优化剪枝
    题目链接:D-PeacefulTeams(atcoder.jp)先看数据范围,肯定是搜索相关首先想到从第1个人,第0个队开始的搜索顺序,因为这属于内部顺序,所以每次搜索要回溯状态,注意要进行大量剪枝#include<bits/stdc++.h>usingnamespacestd;usingull=unsignedlonglong;usingll=lon......
  • LCA 离线tarjan算法
    tarjan算法是离线算法,它必须先将所有的要查询的点对存起来,然后在搜的时候输出结果。tarjan算法很经典,因为算法的思想很巧妙,利用了并查集思想,在dfs下,将查询一步一步的搜出来。伪代码如下:可以看到,对于我们已经保存好的查询,假设为(u,v),u为此时已经搜完的子树的根节点,v的位置就只有两种......
  • hdu 1010 Tempter of the Bone (dfs+奇偶剪枝)
    小记:最开始以为是T时间内,用bfsWA了,后来知道是刚好T时间,然后就用dfs,相当于暴力了,然后简单的dfs提交TLE,必须剪枝。首先判最少需要的时间是否有,没有就不用继续了,而如果有,那么因为我们是要花掉T时间刚好到达,那么我们先保证能走到终点的时间,然后在路上花掉多余的时间此时,我们必须保证......
  • spark如何控制输出到hdfs上的小文件
    项目方案:Spark控制输出到HDFS上的小文件背景介绍在使用Spark进行数据处理和分析时,输出的结果数据通常存储在Hadoop分布式文件系统(HDFS)上。然而,有时输出的结果会被分割成大量的小文件,这可能对后续的数据读取和处理造成性能问题。因此,我们需要一种方法来控制输出到HDFS......
  • Hadoop的hdfs云服务器配置踩坑记录
    本章更多的是通过hdfs的API接口问题角度记录坑点坑点记录一、能够远程访问和通过web端访问hdfs在java代码中添加或更改如下:Configurationconf=newConfiguration();conf.set("dfs.client.use.datanode.hostname","true");//添加此配置信息即可FileSystemfs=FileSys......
  • abc310d <dfs暴搜-分组方案数 / bitmask表示集合+dp>
    题目D-PeacefulTeams参考:https://www.cnblogs.com/legendstane/p/freee-programming-contest-2023-atcoder-beginner-contest-abc-310-solution.htmlhttps://blog.csdn.net/Muelsyse_/article/details/131747083思路方法1dfs暴搜由于数据范围极小,所以直接暴力即可......
  • BFS和DFS基础
    BFS和DFS基础搜索简介搜索是"暴力法"算法的具体实现,是一种吧所有可能的情况都罗列出来,然后逐一检查,从中找到答案的方法。一般步骤找到所有可能的数据,并且永数据结构表示和存储。优化:尽量多的排除不符合条件的数据,以减少搜索空间。用某个算法快速检索这些数据。搜索算法的......