树上问题

· · 个人记录

LCA

LCA，最近公共祖先，一般有两种方法求：倍增和树链剖分。

先弄倍增吧。

简单想想，朴素做法如何求 LCA 呢？

如果两个点深度不同，那我们肯定让深度更深的那个往上跳，直到两点深度相同。

这里特判下这两个点所处位置是否相同，如果相同则返回即可。

如果不相同呢？我们要尽量让它们两个尽可能地靠近它们的 LCA，也就是说都让它们跳到它们 LCA 的子节点上。这样它们下一个父亲就是 LCA。

我们发现一步一步地往上爬实在是太慢了，不妨换种思路。

我们知道任何一个数都可以被二进制拆分掉，那么不妨利用这个性质来波倍增解决问题，也就是说我们先拿大的值来尝试，一直到找到它们的 LCA 为止，但我们要首先预处理一下它们的父亲。

树上差分

一般而言，树上问题都可以类比成序列问题来解决。

序列上能差分，树上怎么就不行呢？

如果我们要让树上从 x 到 y 的点都加点东西的话，我们可以在 x 和 y 两处加上 x，注意，这样会使得 \operatorname{LCA} 被加两次，因此我们要在 \text{LCA} 处减去 x，为了达到差分的目的而不使 \text{LCA} 处没有得到应有的修改，我们要在 \text{LCA} 的父亲那里也减去 x。

一大堆例题

  1. 给定一个 n 个点的树，求一点到另一点的路径点权和。

树上问题类比序列问题，在树上求出每一个点到根节点的点权和（类比前缀和）。

这东西又叫做树上差分。

  1. 给定一个 n 个点的树，有点权，给出 m 次询问，每次给三个数 x, y, z，求 x, y 之间有多少点值等于 z。

开桶，4 差分，\text{vector} 存询问，到一个节点之后把所有的询问处理掉，节点入桶，回溯时删除节点。

  1. 上述问题题面几乎不变，但求 x, y 之间有多少点值小于 z。

把桶换成树状数组。

  1. 给一棵 n 个节点的树，有 m 次询问。每次查询从 x 点开始向 y 点走，每秒走一步，假设在第 i 秒走到了 i 点，则答案加 1，求答案。

推一下式子，满足 \operatorname{dep}(s) - s = \operatorname{dep}(i) - i。

  1. 一棵树，要支持单点加，子树和。

DFS 序转换成一个序列，子树变区间。

  1. 树的直径。

两次 BFS，处理没有负权的情况。