基本定义与前置知识

• 树的 dfs 序：我们称对一棵树 \(T\) 进行深度优先搜索后得到的节点序列为树的 dfs 序。称 \(dfn(u)\) 表示 \(u\) 号点在 dfs 序中的位置。

• 我们称 \(anc(u)\) 为 \(u\) 在树中的父节点，\(dep(u)\) 表示 \(u\) 的深度（一般的，这里的深度定义为经过的点数）。

• 我们称 \(sub(u)\) 为 \(u\) 子树内的所有点，\(son(u)\) 表示 \(u\) 的所有儿子节点。

• 我们称 \(dis(u,v)\) 表示 \((u,v)\) 的距离，\(lca(u,v)\) 为 \((u,v)\) 在树上的最近公共祖先。

最近公共祖先问题相关

求解最近公共祖先

倍增

倍增是最基本的求解最近公共祖先的方法，其复杂度为 \(O(n\log n)\sim O(\log n)\)。

考虑如何暴力求解一对点 \((u,v)\) 的最近公共祖先。每次令 \((u,v)\) 中深度较小的点跳至其父节点，直到两点重合，正确性较为显然。考虑优化这一过程。令 \(anc(u,i)\) 表示 \(u\) 的第 \(2^i\) 级祖先，显然有转移 \(anc(u,i)=anc(anc(u,i-1),i-1)\)。先将 \((u,v)\) 跳到同一深度，然后同时将 \((u,v)\) 上跳直到其有共同的父节点。这两部分显然都可以倍增优化。

倍增求解最近公共祖先优点是可以支持增加叶节点且实现相对简单，缺点是一般来说常数相对较大，且结构稳定，不灵活。

树链剖分

树链剖分也是求解最近公共祖先的一种方式，复杂度为 \(O(n)\sim O(\log n)\)。

树链剖分求解的过程是每次从 \((u,v)\) 中选择所在重链链顶深度最小的点上跳到链顶父亲直到二者位于同一重链，直到二者位于同一重链。此时深度较小的点即为答案。复杂度分析同树链剖分的复杂度分析。

树剖求解最近公共祖先的优势在于其常数相对倍增较小，且可以搭配需要支持树链剖分的题目使用。

dfs 序和欧拉序

由于 dfs 序求解最近公共祖先在代码难度和常数方面均吊打欧拉序，所以本文只介绍前者。

dfs 序求解最近公共祖先可以做到 \(O(n\log n)\sim O(1)\)，实现精细可以做到 \(O(n)\sim O(1)\)，且可以在线回答询问。这使得其相较 tarjan 算法有一定优势。

我们首先求出任意一组 dfs 序。注意到一个性质，对于一对点 \((u,v)\)，若其在树上不构成祖先后代关系，则 \(dfn(lca(u,v))<\min(dfn(u),dfn(v))\)。不妨令 \(dfn(u)<dfn(v)\)，令 \(w\) 为节点满足 \(w\in son(u)\land v\in sub(w)\)，则 \(dfn(u)<dfn(w)<dfn(v)\)，且 \(w\) 为 dfs 序在 \((dfn(u),dfn(v))\) 中深度最小的点。st 表维护即可，答案即为求解出的 \(w\) 的父节点。构成祖先后代关系也是容易判断的。

skip2004 给出了更简洁的写法。具体而言，我们令查询区间变为 \((dfn(u),dfn(v)]\)。注意到对于非祖先后代的情况 \(w\) 依然存在于这个区间里。对于祖先后代的情况，其不成立当且仅当 \(w\) 不存在，即 \(u=v\)。因此此时只需要特判 \(u=v\) 的情况即可。

LNOI2014 LCA

这种求解最近公共祖先的算法只是一种思想，单纯求解没有实用价值。

考虑求解 \((u,v)\) 的最经公共祖先，我们把 \(v\) 到根的路径染色，然后从 \(u\) 向上跳，直到跳到一个有颜色的点，此时该点即为两点的最近公共祖先。这种做法的好处在于将难以表示的 LCA 问题变成了点到根的修改和查询，方便用数据结构或树上差分进行维护。

最近公共祖先相关应用

一般应用于路径问题。对于统计全部路径信息的题目，可以考虑将路径在其最近公共祖先处统计答案。

最近公共祖先还有一些奇怪的结论，我们将其放在下面。

• 对于两条链 \((u_1,v_1),(u_2,v_2)\)，其路径交 \((u',v')\) 不为直链当且仅当 \(lca(u_1,v_1)=lca(u_2,v_2)\)。

• 对于两条链 \((u_1,v_1),(u_2,v_2)\)，若其有交，则其两交点为 \(lca(u_1,u_2),lca(u_1,v_2),lca(v_1,u_2),lca(v_1,v_2)\) 中最深的两个，令其为 \((u',v')\)，且两条路径有交当且仅当 \(u'\neq v'\) 或 \(dep(u')=\max(dep(lca(u_1,v_1),dep(lca(u_2,v_2)))\)。

  正确性证明可以见 panyf 的博客。

例题

快递

题目链接

给 ducati 大跌磕头了/kt。考虑将相交路径分为直链和非直链考虑。

先考虑交成一个直链的部分。首先将给定的路径中的非直链变成两条直链。考虑把每对路径的贡献放在其下交点上计算。对于一个固定的点，考虑所有从子树向上延伸到它的路径，显然在这个点上可能贡献到答案的路径对只有向上延伸的最长的和次长的。因此直接维护最长和次长路径分别是哪条，然后自底向上转移即可。

然后考虑非直链。应用上面的结论，我们把路径 \((u,v)\) 挂到 \(lca(u,v)\) 处计算。然后枚举每一个作为 LCA 的点，将所有挂在上面的路径建出虚树。然后我们在虚树上 dfs。对于枚举到的每一个点 \(u\)，考虑所有经过 \(u\) 向上的路径，一条路径会和另一条路径产生贡献当且仅当其在 \(u\) 子树外的端点的 dfs 序相邻。因此我们对路径按照另一侧的点的 dfs 序维护 set，向上启发式合并即可。

重构树相关

这里的重构树主要指 Kruskal 重构树。下文中我们主要讨论最小生成树意义下的 Kruskal 重构树。

算法流程

对于一棵有边权树 \(T\)，我们按照如下流程构建其 Kruskal 重构树。

令树的边集为 \(E\)，将边按照边权排序，然后依次加入每一条边。同时维护一个森林，初始时是 \(n\) 个孤立点，分别对应了原树上的每一个节点。对于连接 \((u,v)\) 的一条边，新建虚点 \(r\)，将 \(u,v\) 号点所在连通块的根节点向 \(r\) 连边。同时设置 \(r\) 号点的点权为边的边权。

性质

• 性质 1：在不考虑叶节点的情况下，Kruskal 重构树满足堆性质。

  由于按照边权排序，故每个虚点的权值一定严格大于其子节点的点权。

• 性质 2：对于每个节点，其在原树上经过边权不超过 \(w\) 的边能到达的点集等价于在 Kruskal 重构树上其祖先节点中点权不大于 \(w\) 且深度最浅的点的子树中的叶节点集合。

  由性质 1 可以简单推出。这也是 Kruskal 重构树的核心性质。

其实有时我们可以不显示建出 Kruskal 重构树，而是利用 Kruskal 重构树的思想，扫描每一条边，把某些类似于限制“只经过边权不小于 \(d\) 的边能到达的点集” 这样的问题通过维护并查集，在合并连通块时统计答案。

例题

樱符

题目链接

非常坏题目，恨来自中国。

首先考虑树上版本的问题怎么做。注意到此时最大流的限制就是相当于经过边权不小于最大流的边能否到达某个点，因此倒序扫描每一条边，然后维护并查集，每次合并两个连通块时考虑计算答案。注意到当前边一定是限制最大流的那条边，所以 \(maxflow\) 可以直接计算得出。对后面的拆贡献，在每个并查集内维护 \(p^{(s-1)n}\) 的和和 \(p^s\) 的和，其中 \(s\) 为并查集内的点。统计答案的时候直接相乘即可。

然后考虑放到仙人掌上。不妨先强化一下这个问题，对于一般图，我们的做法是建出最小割树，然后跑上面的做法。而仙人掌可以模拟这一过程。具体而言，对于仙人掌上的每一个简单环，我们找出边权最小的边，将其断开，并给其它边加上这条边的权值，得到的树 \(T'\) 即为原仙人掌 \(G\) 的最小割树。实现的时候细节很多。

小 ω 的树

题目链接

依然考虑上面那个题的做法，我们要求子图内边的最小值这样的东西，因此我们不妨枚举这个最小值。注意到在边的最小值确定以后，点一定是越选多越好，那么假设当前扫描的边权为 \(d\)，这个限制与询问只经过边权不小于 \(d\) 的边能到达的点集的点权和等价。因此不妨建出 Kruskal 重构树，考虑维护修改。注意到这个问题在树剖以后相当于是给你两个序列 \(a,b\)，你需要支持区间修改 \(a_i\) 和查询全局 \(a_ib_i\) 的最大值。不妨分块，把每个虚点代表的边对答案的贡献看做 \(kx+b\) 的形式，那么我们实际上就是要求每个块内在 \(x\) 取到某个值的时候的最大直线，那么块内维护凸包即可，修改的时候暴力重构凸包，查询的时候扫一遍凸包，然后凸包上二分查最大值。

虚树

一般适用于复杂度和点个数相关的问题。在此之前，有必要先介绍虚树的定义及其构造过程。

虚树的定义及其构建

给定一棵树 \(T\)，对于一个点集 \(S\)，我们定义 \(T'\) 为 \(S\) 在 \(T\) 上的虚树，当且仅当 \(T'\) 满足如下性质。

• \(\forall u,v\in S,lca(u,v)\in V(T')\)。
• \(\forall (u,v)\in E(T')\)，$u\in sub(v)\lor v\in sub(u) $。
• 在此基础上，最小化 \(V(T')\)。

其中，\(V(T')\) 和 \(E(T')\) 分别表示 \(T'\) 的点集与边集。

我们有两种方法构建虚树。其中一种较为难写且复杂度和精细实现的另一种几乎只有常数差别，所以我们只介绍后者。

首先介绍算法流程。我们维护一个点的序列 \(V\)，初始时 \(V=S\)。

然后我们按照在原树上的 dfs 序将 \(V\) 排序，并把 \(V\) 中相邻两个点的最近公共祖先加入 \(V\)，然后再次排序并去重。得到的 \(V\) 即为 \(V(T')\)。然后我们再次将 \(V\) 按照 dfs 序排序，对于 \(V\) 中的相邻两个点 \(u,v\)，将 \((lca(u,v),v)\) 加入边集，得到的即为 \(E(T')\)。

下面给出做法的正确性证明。我们首先考虑为什么构建的点集是正确的。考虑对于一个点 \(u\in V(T')\) 且 \(u\not \in S\)，由 dfs 序的性质容易发现必定存在两个在 \(S\) 中 dfs 序相邻的点 \(p,q\) 满足 \(lca(p,q)=u\)，然后考虑边集，暴力构建的过程是在原树上标记每一个在 \(V(T')\) 中的点，然后在原树上 dfs，将其向子树内的所有的被标记且没有向上连边的点连边。我们考虑模拟 dfs 的过程，维护一个栈 \(S\)，每次加入一个点 \(u\) 的时候令当前栈顶为 \(v\)，然后弹栈直到栈顶为 \(lca(u,v)\)，将其向 \(v\) 连边并将 \(v\) 压入栈。（注意到此时栈维护的相当于是树上的一条由关键点构成的链。）注意到这个过程中 \(v\) 一定是 \(u\) 在 dfs 序上的前驱，所以我们的做法是正确的。

注意到如果使用上文中介绍的 \(O(1)\) LCA 算法，瓶颈只在于排序。

性质

由虚树的构建过程可知，\(\lvert V(T')\rvert\) 与 \(\lvert S\rvert\) 同阶，那么对于单次询问只涉及到若干关键点这样的问题，我们可以考虑建出虚树并在虚树上计算答案。

例题

快递

可见上文最近公共祖先问题相关的例题部分。

awa

题目链接

这个好（赞赏）。

对于一种颜色 \(c\)，我们称一个点 \(u\) 支配另一个点 \(v\) 当且仅当其为所有颜色为 \(c\) 中的点距离 \(v\) 最近的。如果有多个点我们随意钦定一个。我们称一个三元组 \((l,r,u)\) 为支配三元组，当且仅当 \(u\) 在 \(c(u)\) 上支配了 dfs 序在 \([l,r]\) 中的所有点。

考虑如何求出所有的支配三元组。对于每一种颜色建立虚树，处理出来虚树上每个点的支配点。那么对于一条虚边，相当于是从其代表的祖先后代链中的某一个节点裂开，一半给上面的点支配，一半给下面的支配。根据上述过程不难发现，支配三元组的个数是 \(O(n)\) 的。

然后考虑点分治。把询问点挂到点分树上所在节点到根的每一个点上。然后如果按照 dfn 序和距离分治中心两维作为二维平面的话，修改相当于平面矩形加，查询相当于单点查。因此对于每一个分治中心做扫描线即可。时间复杂度 \(O(n\log^2 n)\)。