DOT 学习笔记

开始大恶补图论了。

说句闲话，\(\text{ODT}\) 和 \(\text{DOT}\)。

\(\text{DOT}\)，全称「树上启发式合并（\(\text{dsu on tree}\)）」，乍一听这个算法十分有智慧的样子，实际上也确实是一个人类智慧，他的本质就是「离线 + 节点合并」，听着复杂度似乎很扯，但是实际上它是正确的，但是我不会证明。

给个例题详细感受一下：

从前有棵树，节点有颜色，每次单点问，子树颜色数，询问 \(\text{1e7}\)，时限 \(1.5\)

首先，直觉告诉我们，这个题如果是树套树的在线做法肯定是 GG 的，因为这个询问次数就不大想让你在线做。

既然我们不能在线做，那我们就把询问离线下来。

首先，在 \(\text{DOT}\) 的眼中，我们只有「重儿子」和「轻儿子」（和重链剖分一样），然后我们进行类似如下的操作：

• 递归遍历轻儿子，计算它们的答案，但不保留影响。
• 递归遍历重儿子，计算它的答案，并保留影响。
• 遍历轻儿子的子树节点，合并轻儿子的答案。

这样，我们遍历了一次重儿子，两次轻儿子，这样肯定是最划算的。

但是为什么可以这么做呢？我也不清楚，但是我们 \(\text{OI-Wiki}\) 上给出了证明，大家可以看一看。