DFS 序和欧拉序复习
图论 OI一道题
今天考试考了这么一道题:
出题人给出一颗以1为根的树, 一开始每个节点都是一颗棋子, 一面白一面黑, 白色的面朝上接下来就q次操作, 操作分两种:
- 0操作: 将一颗棋子翻转
- 1操作:询问一颗棋子与所有面朝上为黑色的棋子lca最深的那个的编号
空间 256M 时间 1.5s, 数据范围 8e5, 考场上果断写树剖, 可惜我人傻常数大, T到75分(有人用树剖过了). 题解是这么说的:


所以要复习一下.
DFS 序
定义: 将树节点按dfs过程中的访问顺序排序,称为 DFS 序.
性质:
- 一个节点和它的子树在一个连续的区间中.
- 进入时间是 dfs 序的反函数, 即 dfs 序中的第i个点的进入时间是i.
欧拉序
树在 dfs 过程中的节点访问顺序称为欧拉序.
欧拉序有很多种, 只要整体满足 dfs 顺序即算欧拉序, 应当按实际需要选择适合的欧拉序. 欧拉序与dfs序不同地方在于, 欧拉序中每个节点可以出现多次, 比如进入一次退出一次, 又比如每次回溯时记录一次。
应用
灵活应用 DFS 序可以在避免树剖的情况下解决一些树上查询和修改问题.
点修改, 子树查询
由性质1, 一个节点和它的子树在一个连续的区间中. 所以这题可以转化为: 点修改, 区间查询. 用树状数组或线段树即可.
树链修改, 单点查询
将一条树链
- x 到根节点的链上所有节点权值加 v.
- y 到根节点的链上所有节点权值加 v.
lca(x, y)
到根节点的链上所有节点权值减 v.fa[lca(x, y)]
到根节点的链上所有节点权值减 v.
即: 节点 x 到根节点链上所有节点的权值加减 v. 修改节点 u 权值, 当且仅当 u 是 v 的祖先节点时, u 对 v 的值有贡献. 所以节点u的权值根等于节点到u节点的链上所有节点和问题. 这就是点修改, 区间和查询问题.
修改操作:
1 | update(l[x], v); |
查询操作:
1 | sum(r[x]) - sum(l[x] - 1) |
树链修改, 子树和查询
修改操作和数组定义同上题.
考虑 u 的子节点 v 对 u 的贡献:
可得到 u 的子树和为:
因此需要两个树状数组或线段树来维护
单点更新, 树链和查询
相当于把第二种情况反过来, 所以将
修改操作:
1 | update(l[x], v); |
查询操作:
1 | sum(l[x]) + sum(l[y]) - sum(l[lca(x, y)]) - sum(l[fa(lca(x, y))]) |
其他
- 子树修改, 单点查询: 区间修改, 单点查询.
- 子树修改, 子树和查询: 区间修改, 区间查询
- 子树修改, 树链查询: 定义
为根节点到y节点的链上所有节点和, 查询和修改操作类似可推.