首页 > 其他分享 >树的序列化笔记

树的序列化笔记

时间:2024-06-22 14:34:01浏览次数:26  
标签:路径 笔记 st DFS 区间 序列化 节点 欧拉

\(dfs\)序

以\(DFS\)(先根遍历)⾸次访问顺序将节点重新排列。

特征:

  1. 每个顶点在序列中出现恰好⼀次(废话)
  2. ⽗节点排在⼦节点前⾯(废话)
  3. 每棵⼦树都占据序列的⼀个区间

欧拉序

记录\(DFS\)递归/回溯时依次经过的所有点。

特征:

  1. 每个点出现次数=度数(根多1次)
  2. 相邻点深度差1
  3. \(LCA(x,y)=\)区间[\(x\)⾸次出现, \(y\)⾸次出现]上深度最⼩的点
    特征3,why?首先,一定经过\(lca\)(已经x->y),1且lca上面的点一定不经过(回溯不会返回,怎么访问到y呢?)。
  4. 循环特征

II类欧拉序:

DFS序:递归u→v时,记v
欧拉序I:回溯u→p(u)时,额外记p(u)
欧拉序II:回溯u→p(u)时,额外记u

相当于进出⼦树u时,都各记录⼀次u

特征:

  1. 每个点u出现恰好2次,下标记为st[u]、ed[u]
  2. 直系路径x→y对应区间[st[x],st[y]]上只出现1次的点

我的感性理解:

DFS序擅长处理子树问题(它是区间)
欧拉序擅长处理各子树之间关系的问题,(各个子树清清楚楚)
II欧拉序擅长处理(非)直系路径的问题(路径清清楚楚)。


例题:

树上带修路径和问询。1887。

题意:有点权的树上,支持点更新,问询树上前缀和:\(S(u)=u\)到根节点的权值和。

\(Solution:\)

->直接维护点,暴力维护答案。
->既然维护点只能暴力维护答案,那我维护答案行不行?
→ u的点更新,会影响哪些节点的S?子树u(树上后缀)
→ DFS序上维护S数组点更新
→ S上的后缀更新前缀查询
→ S上的点查询
→ 线段树 或 差分+BIT

\(Another:\)

II类欧拉序。直系路径x→y对应区间[st[x],st[y]]上只出现1次的点。

从x→y,则⼦树x上
y的子树不会遍历到
侧链上的点都会被记录2次(1进1出)
只有路径上的点记录1次(1进0出)

直系路径在欧拉序上为区间内只出现⼀次的点
→ 考虑路径上的⽬标函数
对应区间上,只要让出现2次的⽆贡献即可
→ st设权值系数*+1,ed设权值系数*-1
路径和=带权区间和,⽤BIT实现
→ ⽬标函数必须有可减性

有依赖的背包问题:

383。
从属关系形成了⼀棵树(加⼀个虚拟根)
选⼦节点必须先选择⽗节点
如不选节点u,其⼦树均不可选
→ 以DFS序后缀为状态状态:\(f[i][j] = dfn[i]≥i的物品放⼊空间j最⼤收益\)

本质后续探究。

换根子树大小问题:

给定⼀棵n个节点的⽆根树,有q个问询:求以X为根时,⼦树Y的节点数,
问询强制在线。n≤100000, q≤2000000
换根后。欧拉回路不变。(欧拉序循环)。
(相当于换了根)。
->子树仍然是个区间。
->区间是啥?\([x后第一次访问到y->最后一次访问到y]\)
转变为求不同值的个数。
->莫队可以,但过不去。
->考虑点对答案的贡献,只有欧拉序首次出现对答案有贡献。
→ 将欧拉序上⾸次出现的位置权值为1,其余为0
-> 求区间和就是⼦树大小。

image

dfs序就是没换根,直接分类讨论了。

离线非直系路径UV(II欧拉序)

\(Solution:\)

→ ⾮直系路径问询x→y
⽅法1:拆成x→lca和lca→y(需可加性)
⽅法2:对应区间[ed[x],st[y]]上
只出现1次的点,但LCA除外。

UV没有可加/可减性怎么办。
->借助计数器,既然变成了区间出现一次点UV问题,可以莫队了。
->出现两次的点怎么维护?怎么知道该加还是该减?
->st+1,ed-1行不行?但是lca左侧ed,右侧st,显然完蛋。
->维护sgn(u)表示u出现次数%2
这样就o了。

image

直系路径和非直系路径对应区间不同!

BFS序

image
->无法转为连续区间,子树不连续。
->按bfs(层级顺序),这不就区间了。
区间加减查询,线段树,over.

→ 邻集N(u)=u及其所有相邻点(星型⼦图)
树上的邻集N(u)={u,p(u)} ∪ Son(u)
DFS/欧拉序上,Son(u)不是区间
→ BFS序上,Son(u)是区间
操作2,3:1~2次点更新 + 0~1次段更新
BFS序上建线段树,Over

image

混合序

各类序列化其本质思想是使树上节点尽量有序。

题意:
(有根)树上在线问询
操作1:\(将⼦树u中(以u为根的相对)深度≤k的点权+c\)
操作2:\(求⼦树u中深度≤k的权和\)

->bfs序交子树节点太多。
->dfs序是个区间,好处理。转变为求depth在一定区间内的点和。
->把点视为二维,二维线段树or二维差分前缀和,over

标签:路径,笔记,st,DFS,区间,序列化,节点,欧拉
From: https://www.cnblogs.com/qinyiting/p/18261909

相关文章

  • Hive笔记-4
    240618-Hive笔记-44.2Insert4.2.1将查询结果插入表中1)语法INSERT (INTO |OVERWRITE)TABLE tablename[PARTITION (partcol1=val1,partcol2=val2...)]select_stamement;关键字说明:(1)INTO:将结果追加到目标表(2)OVERWRITE:用结果覆盖原有数据2)案例......
  • Linux驱动开发笔记(九)IIC子系统及其驱动
    文章目录前言一、IIC驱动框架二、总线驱动2.1iic总线的运行机制2.2重要数据结构2.2.1i2c_driver结构体2.2.2i2c总线结构体2.3匹配规则三、设备树的修改四、设备驱动的编写4.1相关API函数4.1.1i2c_add_adapter()4.1.2i2c_register_driver()4.1.3i2c_transfer......
  • Effective C++ 改善程序与设计的55个具体做法笔记与心得 4
    四.设计与声明18.让接口容易被正确使用,不易被误用请记住:好的接口很容易被正确使用,不容易被误用。你应该在你的所有接口中努力达成这些性质“促进正确使用”的办法包括接口的一致性,以及与内置类型的行为兼容。“阻止误用”的办法包括建立新类型、限制类型上的操作、束缚......
  • FFmpeg开发笔记(三十一)使用RTMP Streamer开启APP直播推流
    ​RTMPStreamer是一个安卓手机端的开源RTMP直播推流框架,可用于RTMP直播和RTSP直播,其升级版还支持SRT直播(腾讯视频云就采用SRT协议)。RTMPStreamer支持的视频编码包括H264、H265、AV1等等,支持的音频编码包括AAC、G711、OPUS等等,可谓功能强大的APP直播框架。由于升级版的RTMPStre......
  • day09 | KMP算法笔记
    目录一、KMP算法有什么用?二、构建next数组(就是前缀表)1)什么是前缀表(next数组)2)前缀表有什么用3)前缀表怎么记录的?4)为什么一定要用前缀表5)构建next数组三、力扣28.实现strStr()四、拓展题重复的子字符串一、KMP算法有什么用?该算法主要应用在字符串匹配上,当模式串与......
  • TVM学习笔记
    安装podman拉取镜像podmanpulltlcpack/ci-gpu:20240105-165030-51bdaec6podmanrun-it--network=host--gpusall--shm-size=10g-v/home/moguw/Github/tvm-learn:/workspace--nametvm-buildtlcpack/ci-gpu:20240105-165030-51bdaec6/bin/bash--shm-size=10g指......
  • 【YOLOv8改进】MLCA(Mixed local channel attention):混合局部通道注意力(论文笔记+引
    摘要本项目介绍了一种轻量级的MixedLocalChannelAttention(MLCA)模块,该模块同时考虑通道信息和空间信息,并结合局部信息和全局信息以提高网络的表达效果。基于该模块,我们提出了MobileNet-Attention-YOLO(MAY)算法,用于比较各种注意力模块的性能。在PascalVOC和SMID数......
  • 【YOLOv8改进】BRA(bi-level routing attention ):双层路由注意力(论文笔记+引入代码)
    摘要作为视觉Transformers的核心构建模块,注意力机制是一种强大的工具,用于捕捉长程依赖关系。然而,这种强大功能也带来了代价:计算代价巨大且内存占用高,因为需要计算所有空间位置上成对的token交互。为缓解这一问题,一系列研究尝试通过引入手工设计且内容无关的稀疏性来改进注意力机......
  • AMBA总线笔记1-APB设计要点
    1.APB2框架    APB是一种低功耗、低速度外设总线,主要用于连接外围设备和低速外设,如定时器、GPIO(通用输入输出)、串口控制器等。因其低功耗和相对简单的设计,适合于对性能要求不高的外设连接。        在实际的SOC架构中,APB往往就以以下形式出现:    A......
  • AMBA总线笔记2-AHB协议
    1.AHB介绍和组成    AHB是针对高频率高频宽及快速系统模块设计的总线,构成包括主设备master、从设备slave、仲裁器arbiter、译码器decoder。每个AHB都需要一个仲裁器和一个译码器且只有一个。2.AHB、AXI、APB对比总线AHBAXIAPB宽度32,64,128,2568,16,32,64,128,256,512,10248,1......