正文篇

第四章 DFS 树与图上应用

$4.1$ DFS 信息传递

根据所放位置的不同，信息传递的先后会有差异。

如将 信息传递的代码 放在递归函数的 前面，就是 先更新信息，再搜索下一个阶段。

若是放在 后面 就会导致，只有将这一条链搜完之后才可以从 最底层的阶段往上 维护信息。

这就是信息传递的两种形式：由后向前 和 由前向后。

如 带权并查集 对 权值维护 的搜索顺序就是 由后向前 维护权值，再从代表元起 由前向后 更新节点。

$4.2$ DFS 信息维护

* 整体思想

【例题 1】 传染病控制

本题题意：

有一棵树，你需要在这棵树的 每一层 找到一个子树砍掉，求剩余子树的 最小值。

确实我们要维护的信息 子树的数量 后暴力枚举即可。

需要注意的是 删掉子树 的操作怎么实现，以下提供一种解决途径：

一、给子树的所有边 染色，相当于 标记数组。

注意要对这棵树 分层 以便于枚举。

【例题 2】 表达式

本题是 后缀表达式 读入，可以直接用 一个栈， 每读到符号时，就弹出变量。

由于题目中的变量都是 布尔值，容易储存管理，可以想一下是否能用一种方便的形式 打包处理。

通过 $Trie$ 树，我们可以想到用树形结构储存可以降低查找的时间，但遍历统计值又太麻烦。

不过本题的所有询问都是 无后效性的，

所以，可以考虑预处理一下 哪些值更改会影响答案，预处理完，就可以 $O(1)$ 回答了！

代码

* 特殊性质

【例题 1】 树的直径

结论 1

找出树的直径的算法步骤为：

• 任选一点为 $u$
• 找到距离 $u$ 最远的节点 $v$
• 找到距离 $v$ 最远的节点 $f$
• $v$ -> $f$ 是树的一条直径

我们用反证法：

设 树的一条直径 为 $b$ -> $c$

则 $b$ -> $c$ 和 $u$ -> $v$ 之间有两种可能情况。

若 $b$ -> $c$ 和 $u$ -> $v$ 不相交，则分别两路径上选一点，连接为 $x$ -> $y$

因为 $u$ -> $v$ $>=$ $u$ -> $c$

所以 $v$ -> $y$ $>=$ $y$ -> $x$ -> $c$

进而 $v$ -> $y$ -> $x$ $>=$ $x$ -> $c$

则 $v$ -> $y$ -> $x$ -> $b$ $>=$ $b$ -> $c$

所以 $v$ -> $f$ $>=$ $b$ -> $c$

又因为 $b$ -> $c$ 为树的一条直径，所以 $v$ -> $f$ 也为树的一条直径。

若 $b$ -> $c$ 和 $u$ -> $v$ 相交，其交点为 $g$

则 $v$ -> $g$ $>=$ $g$ -> $c$

进而 $v$ -> $g$ -> $b$ >= $b$ -> $c$

所以 $v$ -> $f$ $>=$ $b$ -> $c$

又因为 $b$ -> $c$ 为树的一条直径，所以 $v$ -> $f$ 也为树的一条直径。

引理 1

若边权为非负数，则直径的中点相同。

这是因为任意的直径若是相交再分开，则两部分相等。

两线重叠部分任意都满足这个性质。

若是不相交，则存在更长的直径，比如 分类 1 中

若 $v$ -> $f$ $==$ $b$ -> $c$

则 $v$ -> $b$ == $b$ -> $c$

$v$ -> $x$ == $x$ -> $b$

反证法，假设 $x$ 不为 $b$ -> $c$ 中点

设中点为 $e$，则 $b$ -> $e$ > $b$ -> $x$ = $v$ -> $x$

这与 $v$ -> $b$ $==$ $b$ $->$ $c$ 相违背，

$x$ 是中点，则 $x, y$ 重合。

证毕。

引理 2

在一棵树中，求不同的结点 $A、B、C$，有 $max(min(dist[A][C], dist[B][C]) + dist[A][B])$。

则 $A$ -> $B$ 为树上直径。

证明与结论证明类似，自证不难。

我们若是以 $C$ 为起点运行 结论 1，此时令 $A$ -> $B$ 为直径，

令 $min(dist[A][C], dist[B][C])$ 尽量大即可。

【例题 2】 树的中心

一道练习 信息传递方向 的好题。

让我们再回顾一下信息传递的两个方向：由前往后 和 由后往前。

概括性解释的话，就是用 $DFS$ 实现的 递推 和 递归。

那这两个概念的本质如下：

递推：由已知推未知, 呈发散性
递归：逆序的递推, 呈收敛性

再让我们解析一下本题所需的两个 $DFS$ 函数。

第一个函数，求子树内的节点对当前节点的贡献。

为什么这要 由后往前 计算？

这其实并不好理解，倒不如用 反证法 想一下为什么不能 由前往后。

因为这个函数要求计算的是其 子树，若由前往后，则祖先节点值已知，其子树值未知。

这不是满足了 由已知推未知 吗？

没有，因为我们要做的是 由子树推其祖先，所以顺序出错了，正确的顺序是 由后往前

第二个函数，父亲节点对当前节点的贡献。

此时我们不需要靠子节点，就能计算出父节点的贡献，而由父节点推子节点也恰好符合 由前往后 的要求。

若这么计算，没办法计算出 祖先节点 的贡献值，就可以 事先预处理 或 建虚拟源点