首页 > 其他分享 >dfs 序 O(nlogn)-O(1) 求 LCA

dfs 序 O(nlogn)-O(1) 求 LCA

时间:2023-09-20 19:35:41浏览次数:43  
标签:int 深度 dfs st dfn LCA nlogn

学点分树,发现不会询问复杂度 \(O(1)\) 的 LCA。于是被迫递归式学习。

我们设 \(dfn_i\) 表示点 \(i\) 在 dfs 过程中第几个被访问到,把点按访问到的顺序排序得到的序列叫 dfs 序。
考虑 \(u\) 和 \(v\) 在 dfs 序上的位置之间的这一段序列有什么。
设 \(lca(u,v)=x,dfn_u<dfn_v\)。那么 \(x\) 到 \(v\) 路径上第一个点(即 \(v\) 所在的 \(x\) 的子树)一定在 \(u\) 和 \(v\) 之间。
而这个点就是 \(u\) 到 \(v\) 之间深度最小的点。\(lca(u,v)\) 就是 \(u\) 到 \(v\) 深度最小的点的父亲。

区间深度最小值用 ST 表维护。注意到 \(u\) 是 \(v\) 的祖先时深度最小的点会变成 \(u\),我们改为在 \([dfn_u+1,dfn_v]\) 的区间上查询。

代码封装了一下。

struct LCA
{
    int dfn[N],tot,dep[N],st[20][N];
    il int get(int x,int y) {return dep[x]<dep[y]?x:y;}
    void dfs(int u,int fa)
    {
        dfn[u]=++tot,st[0][tot]=fa; dep[u]=dep[fa]+1;
        for(int i=head[u];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,u);
    }
    il void init()
    {
        dfs(rt,0);
        for(int i=1;(1<<i)<=n;i++)
            for(int j=1;j<=n-(1<<i)+1;j++)
                st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
    }
    il int lca(int x,int y)
    {
        if(x==y) return x;
        if((x=dfn[x])>(y=dfn[y])) swap(x,y);
        int l=__lg(y-x);
        return get(st[l][x+1],st[l][y-(1<<l)+1]);
    }
}l;

标签:int,深度,dfs,st,dfn,LCA,nlogn
From: https://www.cnblogs.com/ying-xue/p/17718176.html

相关文章

  • hdfs副本数设置
    1.调整HDFS副本数##该命令只会设置当前已有的文件副本数,不会改默认副本数参数hadoopfs-setrep-R-w5/corelogs2.查看HDFS当前文件副本数hadoopfs-ls/corelogs##显示的第二个参数即为当前副本数......
  • HDFS入门
    HDFS的块大小设计原则HDFS常用shell命令HDFS的读写流程第一章HDFS概述1.1HDFS产生背景和定义1.1.1产生背景大数据时代,需要一种系统来管理多台机器上的文件,这就是分布式文件管理系统,HDFS就是分布式文件管理系统的一种1.1.2HDFS定义HDFS(HaddopDistributedFile......
  • 多叉树应用 包括构建 dfs遍历
    力扣17.电话号码的字母组合给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。示例1:输入:digits="23"输出:["ad","ae","af","bd","be","bf","cd","ce&quo......
  • 6576: 点的距离 倍增LCA
    描述 给定一棵n个点的树,Q个询问,每次询问点x到点y两点之间的距离。 输入 第一行一个正整数n,表示这棵树有n个节点;接下来n−1行,每行两个整数x,y表示x,y之间有一条连边;然后一个整数Q,表示有Q个询问;接下来Q行每行两个整数x,y表示询问x到y的距......
  • HDFS体系结构
    HDFS体系结构HDFS支持主从结构,主节点称为NameNode,是因为主节点上运行的有NameNode进程,NameNode支持多个,目前我们的集群中只配置了一个从节点称为DataNode,是因为从节点上面运行的有DataNode进程,DataNode支持多个,目前我们的集群中有两个HDFS中还包含一个SecondaryNameNode进程,......
  • 【dfs基础题】洛谷P1219题解
    题目大意给定棋盘的规格为\(n×n\),现在要摆\(n\)个皇后,使得每个皇后不能互相攻击。题目解答由题意可知,如果两个皇后在同一行或同一列或同一对角线,那么就会互相攻击。那么就简单了,若当前要摆的是第\(i\)个皇后,那么只需要for循环一遍前面的\(i-1\)个皇后,判断前面的皇后......
  • HDFS的常见Shell操作
    HDFS的常见Shell操作直接在命令行中输入hdfsdfs,可以查看dfs后面可以跟的所有参数。详细使用方法请参考官方文档。注意:这里面的[]表示是可选项,<>表示是必填项[hadoop@hadoop81hadoop]$hdfsdfsUsage:hadoopfs[genericoptions] [-appendToFile<localsrc>...<dst>] [-cat......
  • 科技:dfn 求 LCA
    upd:2023.09.13新建非常好思路,学习自Alex_Wei。摘要使用st表维护区间内所有点的dfn最小的父节点。优点是好写、时间空间常数小。前置约定\(dfn_{i}\):\(i\)是第几个被访问的点\(sub_{i}\):以\(i\)为根的子树\(LCA\):\(\text{LCA}(u,v)\)原理dfn的性质:设\(......
  • 使用Python调用Hadoop Hdfs的API
    一、Java调用hdfs的apiimportorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.fs.FileSystem;importorg.apache.hadoop.fs.Path;importorg.junit.After;importorg.junit.Before;importorg.junit.Test;importjava.io.IOException;importjava.net......
  • RTMP视频服务器EasyDSS互联网视频直播点播平台如何基于FastDFS、ffmpeg、videojs实现
    互联网视频直播点播EasyDSS平台能实现视频流媒体的上传、转码、存储、录像、推流、拉流、直播等功能,在场景上,可以应用到互联网教育、在线课堂、游戏直播、视频点播、无人机等领域。 视频点播平台是指提供用户上传、存储和播放视频内容的在线平台。它可以让用户随时随地观看各......