\(dfs\)序
以\(DFS\)(先根遍历)⾸次访问顺序将节点重新排列。
特征:
- 每个顶点在序列中出现恰好⼀次(废话)
- ⽗节点排在⼦节点前⾯(废话)
- 每棵⼦树都占据序列的⼀个区间
欧拉序
记录\(DFS\)递归/回溯时依次经过的所有点。
特征:
- 每个点出现次数=度数(根多1次)
- 相邻点深度差1
- \(LCA(x,y)=\)区间[\(x\)⾸次出现, \(y\)⾸次出现]上深度最⼩的点
特征3,why?首先,一定经过\(lca\)(已经x->y),1且lca上面的点一定不经过(回溯不会返回,怎么访问到y呢?)。 - 循环特征
II类欧拉序:
DFS序:递归u→v时,记v
欧拉序I:回溯u→p(u)时,额外记p(u)
欧拉序II:回溯u→p(u)时,额外记u
相当于进出⼦树u时,都各记录⼀次u
特征:
- 每个点u出现恰好2次,下标记为st[u]、ed[u]
- 直系路径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
-> 求区间和就是⼦树大小。
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了。
直系路径和非直系路径对应区间不同!
BFS序
->无法转为连续区间,子树不连续。
->按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
混合序
各类序列化其本质思想是使树上节点尽量有序。
题意:
(有根)树上在线问询
操作1:\(将⼦树u中(以u为根的相对)深度≤k的点权+c\)
操作2:\(求⼦树u中深度≤k的权和\)
->bfs序交子树节点太多。
->dfs序是个区间,好处理。转变为求depth在一定区间内的点和。
->把点视为二维,二维线段树or二维差分前缀和,over