DFS 序和欧拉序复习

一道题

今天考试考了这么一道题:

出题人给出一颗以1为根的树, 一开始每个节点都是一颗棋子, 一面白一面黑, 白色的面朝上接下来就q次操作, 操作分两种:

• 0操作: 将一颗棋子翻转
• 1操作:询问一颗棋子与所有面朝上为黑色的棋子lca最深的那个的编号

空间 256M 时间 1.5s, 数据范围 8e5, 考场上果断写树剖, 可惜我人傻常数大, T到75分(有人用树剖过了). 题解是这么说的:

image.png

image.png

所以要复习一下.

DFS 序

定义: 将树节点按dfs过程中的访问顺序排序，称为 DFS 序.

性质:

1. 一个节点和它的子树在一个连续的区间中.
2. 进入时间是 dfs 序的反函数, 即 dfs 序中的第i个点的进入时间是i.

欧拉序

树在 dfs 过程中的节点访问顺序称为欧拉序.

欧拉序有很多种, 只要整体满足 dfs 顺序即算欧拉序, 应当按实际需要选择适合的欧拉序. 欧拉序与dfs序不同地方在于, 欧拉序中每个节点可以出现多次, 比如进入一次退出一次, 又比如每次回溯时记录一次。

应用

灵活应用 DFS 序可以在避免树剖的情况下解决一些树上查询和修改问题.

点修改, 子树查询

由性质1, 一个节点和它的子树在一个连续的区间中. 所以这题可以转化为: 点修改, 区间查询. 用树状数组或线段树即可.

树链修改, 单点查询

将一条树链上的所有点的权值加, 可分为以下步骤:

1. x 到根节点的链上所有节点权值加 v.
2. y 到根节点的链上所有节点权值加 v.
3. lca(x, y) 到根节点的链上所有节点权值减 v.
4. fa[lca(x, y)] 到根节点的链上所有节点权值减 v.

即: 节点 x 到根节点链上所有节点的权值加减 v. 修改节点 u 权值, 当且仅当 u 是 v 的祖先节点时, u 对 v 的值有贡献. 所以节点u的权值根等于节点到u节点的链上所有节点和问题. 这就是点修改, 区间和查询问题.

修改操作:

update(l[x], v);
update(l[y], v);
update(l[lca(x, y)], -v);
update(l[fa(lca(x, y))], -v)

查询操作:

sum(r[x]) - sum(l[x] - 1)

树链修改, 子树和查询

修改操作和数组定义同上题.

考虑 u 的子节点 v 对 u 的贡献:

可得到 u 的子树和为:

因此需要两个树状数组或线段树来维护 和 的区间和.

单点更新, 树链和查询

相当于把第二种情况反过来, 所以将 定义为差分前缀和, 即的权值等于 dfs 中 的区间和.

修改操作:

update(l[x], v);
update(r[x] + 1, -v)

查询操作:

sum(l[x]) + sum(l[y]) - sum(l[lca(x, y)]) - sum(l[fa(lca(x, y))])

其他

• 子树修改, 单点查询: 区间修改, 单点查询.
• 子树修改, 子树和查询: 区间修改, 区间查询
• 子树修改, 树链查询: 定义 为根节点到y节点的链上所有节点和, 查询和修改操作类似可推.