DFS 序入门

本文秉持小学生也能看懂的水准，因此会比较啰嗦。（是的这和 #52 是一个系列的）

大佬建议略读即可。

-1 前置技能

树状数组；基本的树和图的概念；DP 入门知识

0 文章提要

• DFS 序的定义；
• DFS 序模板题，配合树状数组、树上差分食用；
• DFS 序在树形 DP 中的应用（比如替代多叉树转二叉树）；
• 其他运用了 DFS 序的算法 & 数据结构的科普，包括 Tarjan 算法和 Link-Cut Tree；
• 欧拉序与 LCA（不过欧拉序一般来说不视为 DFS 序）。

1 定义

DFS 序似乎并没有一个明确且公认的定义，下文中我所说的「有根树的 DFS 序」指的是「结点在深搜中被访问的顺序」。比如这棵树——

这棵树的 DFS 序列就是 C 1 A E 7 H B 8 3 4 F 5 6 9 I G 2 D，每个结点的 \tt{dfn} 即为：

结点编号\;	C\;	1\;	A\;	E\;	7\;	H\;	B\;	8\;	3\;	4\;\;	F\;\;	5\;\;	6\;\;	9\;\;	I\;\;	G\;\;	2\;\;	D
\tt{dfn}	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18

定义子树 x 表示结点 x 及其所有的子孙结点，该序列有一个很重要的性质：
每棵子树 x 在 DFS 序列中一定是连续的一段，结点 x 一定在这段的开头。 举几个例子：

C 1[A E 7 H B 8 3 4 F]5 6 9 I G 2 D
          子树A

C 1 A[E 7 H B]8 3 4 F 5 6 9 I G 2 D
       子树E

C 1 A E 7 H B 8 3 4 F[5 6 9 I G 2 D]
                          子树5

C 1 A E 7 H B 8 3 4 F 5[6 9]I G 2 D
                       子树6

这使得在子树上进行的修改、查询可以转化为区间修改、区间查询。结合树状数组 or 线段树食用均可。

模板 LibreOJ #144, #145。

2 DFS序与树上差分

LibreOJ #146. DFS 序 3，树上差分 1

给一棵有根树，这棵树由编号为 1\dots N 的 N 个结点组成。根结点的编号为 R。每个结点都有一个权值，结点 i 的权值为 v_i。
接下来有 M 组操作，操作分为两类：

• 1 a b x，表示将「结点 a 到结点 b 的简单路径」上所有结点的权值都增加 x；
• 2 a，表示求结点 a 的权值。
• 3 a，表示求 a 的子树上所有结点的权值之和。

对于所有数据，$1\leqslant N, M\leqslant 10^6,$ $1\leqslant R\leqslant N,$ $-10^6\leqslant v_i, x\leqslant 10^6$.

老是有人说「这套模板题不是树剖裸题吗」「O(N\log N) 咋做啊」，因此我过来写一下题解（这套题写题解感觉没啥意思啊）。下面先介绍树上差分，你学过树上差分的话可以跳过下面这一段。

先说不含操作 3 的情况。

我们发现我们可以高效的进行区间查询，但无法高效地直接处理树链（对这题来说 \log^2 N 不够高效）。那我们能否想办法以提升查询操作的时间为代价，来减少修改操作的时间复杂度呢？

（假设是给结点 u 到结点 v 的树链上每个结点加上 x）先考虑一种较简单的情况：修改的结点中，u 是 v 的祖先。

请在 DFS 序列中划出子树 A, E, 7 所占的区间。

可以发现，较浅结点（A）的区间会完全包含较深结点（E,7）的区间。因此，只要在结点 7 上加上 x，查询结点 A, E, 7 时，在该结点的子树内就会包含该修改。一言以蔽之：树链修改 -> 单点修改，单点查询 -> 子树查询。

但这还会波及其他「子树中包含结点 7」的结点，比如结点 1。因此我们需要在结点 1 处减去 x。

「u 是 v 的祖先」的这种特殊情况已经解决了，至于更一般的情况，你应该能猜出要如何修改了：拆成 u 到 lca，以及 v 到 lca（但这半条不含 lca 这个端点）这两条链即可。

接下来我们把操作 3 也考虑进来。可以猜测做法仍然是树上差分。在这之前，我们先用一句话总结一下上面的做法：

不妨考虑一种更简单的树链修改：给出一个结点 u，给「该结点到树根」的路径上所有结点加上 x。

p7.png

如上图，差分后只需修改结点 7。请思考一下：修改结点 7 会对哪些结点上的查询有影响？显然是结点 7 的祖先结点 E, A, 1, C。

给结点 7 加上 x 后，当查询结点 E 时，实际上要在结果中加上 2x（因为结点 E 的子树中，E 和 7 在树链上，都被加上了 x）；当查询结点 A 时要加上 3x；以此类推，查询结点 1, C 时要加上 4x, 5x。

由此可以看出，（设 v 是 u 的祖先）u 的修改对 v 的影响和 x 以及两结点的深度差有关，具体来说， 如果在结点 u 加上了 x，那么查询子树 v 的答案中就得加上 (depth_u - depth_v)\times x。

这里补充一句这个 depth 数组。

我们留意到，一般情况的树链修改可以被拆成两条链，这两条链都满足：一个端点是另一个端点的祖先。而这种「u 是 v 的祖先」的链还可以看成由两条链组成：「u 到树根」以及「v 到树根」。

LibreOJ #147. DFS 序 4

给一棵有根树，这棵树由编号为 1\dots N 的 N 个结点组成。根结点的编号为 R。每个结点都有一个权值，结点 i 的权值为 v_i。
接下来有 M 组操作，操作分为三类：

• 1 a x，表示将结点 a 的权值增加 x；
• 2 a x，表示将 a 的子树上所有结点的权值增加 x；
• 3 a b，表示求「结点 a 到结点 b 的简单路径」上所有结点的权值之和。

（TODO）

思考题　其实是我不清楚行不行所以问你　如果出成子树修改+树链修改+子树查询，或是子树修改+子树查询+树链查询，是否可做?

习题

1. BZOJ 3306

   给定一棵大小为 n 的有根点权树,支持以下操作: • 换根 • 修改点权 查询子树最小值

\textcolor{grey}{a+b}

3653, 2819, 3611

HDU: 5039, 3974, 5692, 5877, 5293, 5296, 3887

树上差分的模板题请左转洛谷日报 #76. 差分数组 and 树上差分