营员交流课件
链接: http://pan.baidu.com/s/1hrM1Ic8 密码: dc4j
概述
随着业界毒瘤的推动，我们开始见到越来越多的仙人掌题。对于这种题，我们总是想办法把仙人掌转化为树来做，从而将熟悉的树的算法修改后用于仙人掌上。
圆方树是一种由我们提出的树的结构，它能轻松的将仙人掌转化为树，并能资磁仙人掌上点分治、虚仙人掌、仙人掌剖分等经典的树上问题，在 UOJ 上若干道仙人掌题目中，均有极高的效率。
构造
首先我们要构造原仙人掌 $G$ 的圆方树 $T_G$。我们定义原仙人掌上的点为圆点，现在我们考虑转化。
我们对仙人掌进行点双的 Tarjan 算法，因为仙人掌上每个环都是一个点双，而且在栈中的顺序就是环上点的顺序。那么考虑一个点 $i$ 的一条出边 $（i,j)$ 满足 $dfn(i) < low(j)$，那么说明 $(i, j)$ 是一条树边，我们在 $T_G$ 中直接连上这两个点即可；如果 $dfn(i) = low(j)$，那么我们找到了一个环（可能是重边造成的二元环），则从栈中取出点直到取出 $j$ 为止，设这样从栈中取出的点集为 $R$，则 $R \cup \{i\}$ 是一个环；对于其他情况，我们按照 Tarjan 的步骤执行即可，无需特殊处理。
对于一个环 $R \cup \{i\}$，设 $i$ 为环的 根。我们新建一个方点 $P$，在 $T_G$ 中连接所有的 $(P, q), q\in R \cup \{i\}$。这样连的边数等于环上点数，而点又多了一个，因此最后连出的 $T_G$ 是树。
性质
圆方树有优美的性质。
无论如何换根，圆方树形态不变 //因为你是把环连成菊花而不是别的什么
圆方树的子树 = 原仙人掌的子仙人掌 //分类讨论各种情况可以证明
方点不会和方点相连
还有其他神奇的性质，要具体题目具体分析。
应用
最短路
类比树上最短路，我们在 LCA 处考虑。然而圆方树的树上距离并不一定就等于仙人掌上的最短路长度。
注意到圆方树中的边权都还没有确定，那么我们就可以现在确定了。如果一条边是圆圆边（圆点指向圆点的边，这里已经任意选择一圆点为根），那么它是一个树边，边权等于原仙人掌上边权；如果是方圆边，那么边权等于环的根到那个圆点的最短路径长度；如果是圆方边，那么边权为 0。
这样，如果一对询问点在圆方树上的 LCA 是圆点，那么其圆方树上长度就是原仙人掌上长度，因为路径上唯一的不同就在于对于每个环是走哪一侧（这个决策对每个环是独立的），而前面边权的确定已经解决了这一问题；如果 LCA 是方点，则我们只需要考虑在 LCA 这个环中是否要走经过根的那一侧。我们需要找出这两个询问点 $(x, y)$ 分别是在这个方点的哪两个儿子 $(p_x, p_y)$ 的子树中（这就是个 jump 操作，可以用倍增或树链剖分轻松实现）。则 $x \rightarrow p_x$ 和 $p_y \rightarrow y$ 的树上距离都是最短路径，现在就只需要考虑同一个环上的点 $(p_x, p_y)$ 的最短路径（其实也就是走哪一侧的问题）。 前面先记录环上边权的前缀和，这样就能 $O(1)$ 计算出不经过根那条路径的长度，再通过记录整个环的边权和比较出走哪一侧更优。
例题：http://www.lydsy.com/JudgeOnline/problem.php?id=2125
DP
仙人掌有若干种 DP，比如最大独立集和直径。
最大独立集比较简单，只需要 DFS 时，树边按照树上独立集的方式转移，环上用一个 $f(i, 0..1, 0..1)$ 的简单 DP 去转移即可。
例题：http://www.lydsy.com/JudgeOnline/problem.php?id=4316
求直径的话，我们类比求树直径的方式，在 LCA 处考虑。设 $f(i, j \in {1,2})$ 为 $i$ 子树中的第 $j$ 深的点，那么圆点可以轻松转移、更新答案。在方点转移也容易，但更新答案不能直接更新（因为有哪一侧的问题，直接取不一定是最短路，会导致答案偏大）。我们可以把环复制一份用单调队列来解决，也可以正反各做一次前缀和。
例题：http://www.lydsy.com/JudgeOnline/problem.php?id=1023
虚仙人掌
对一个点集的子集进行询问。分例题进行讲解。
UOJ 87
题意：给出一个点集，求点集中两两最短路径的最大值。
首先对原仙人掌建立 BZOJ 2125 那种带边权的圆方树。然后每次对圆方树建立虚树，在虚树上按照 BZOJ 1023 的方法进行简单 DP 即可。
UOJ 189
题意：给出仙人掌，要求资磁：(1)询问若干条最短、最长路径的并的边权和 (2)修改边权
先对所有端点的点建立圆方树的虚树。现在我们要考虑两部分的贡献：（1）对于虚树上一条边，对应圆方树上一条链，我们要一起考虑这条链的贡献；（2）对于虚树上的一个方点，对应一个环，我们要考虑它有哪几段计入答案。
我们对于每条边这么操作：首先找到 LCA，判断出是哪一段符合要求（最长或最短），然后像求圆的周长（某些计算几何题）那样记录两个括号用来扫描线；然后找出不在环上的一段（如果 LCA 是方点，要利用 jump 操作求出 $p_x, p_y$），利用子树前缀和的思想记录一下是否存在最长、最短路的询问（也就是在 $x$ 处 $+1$，在 $p_x$ 处 $-1$，然后一个点的权值为其子树中的权值之和）。
那么对于一条虚树上的边，我们就有 4 种情况，表示最长路和最短路分别是否有。我们可以通过一种特殊的“深度”来计算这些值。设 $f(i)$ 为从圆方树根到 $i$ 的树边长度之和，$g(i)$ 为从根到 $i$ 的最短路径，$h(i)$ 为从根到 $i$ 的最长路径。那么如果经过边$(i, j)$的又有最长路径又有最短路径，则贡献为 $g(j) + h(j) - f(j) - (g(i) + h(i) - f(i))$；如果只有最短路径则贡献为 $g(i) - g(j)$，只有最长路径贡献为 $h(i) - h(j)$。
环上的情况，我们像求圆上周长那样，对之前添加的括号排个序即可。
如果要修改，那么既有可能影响环上距离，又有可能影响那 3 种深度。我们分别用树状数组维护均可。注意如果修改的是环上的边，那么影响的深度数组到底是哪几段需要分类讨论。
点分治
UOJ 23
题意：求出仙人掌上从 1 出发长度为 $[1..n]$ 的简单路径的条数。
暴力是用背包的思想，设 $f(i, j)$ 表示从 $i$ 出发往下走 $j$ 步的路径条数。注意到转移是卷积的形式，那么我们可以用 FFT 来解决这一问题。
进行点分治。设当前子树中重心为 $G$，考虑求出 $f(G)$ 为这棵子树的背包数组。首先 $G$ 的包含当前连通块最高点（记为 $top(G)$）这一分支可以递归去做。现在考虑 $G$ 的儿子们，如果 $G$ 是圆点，那么直接把出边的 $f$ 加起来求和即可；否则如果是方点，那么每个儿子都有两种选择：向左或向右，两种情况都要加上去。现在还需要考虑 $top(G)$ 到 $G$ 这一段对 $G$ 出边贡献的 $f$ 的影响。显然我们可以再套一个分治 FFT 把 $top(G)$ 到 $G$ 这一条链上的数组算出来，但这样太笨了。我们维护 $g(G)$ 表示 $top(G)$ 到 $G$ 这一段的背包数组，那么我们发现从 $fa(G)$ 开始一直跳 $top$，一段一段跳上去，不会超过 $\log(top(G)\ 到\ G\ 的链长)$ 段，而且后一段的 $g$ 数组长度是前一段的两倍。这样暴力 FFT 卷积起来，复杂度只有 $top(G)\ 到\ G\ 的链长 \times \log(top(G)\ 到\ G\ 的链长)$，那么这个问题就在 $O(n \log^2 n)$ 的时间内完美解决。
一个细节是设方点点权为环的大小，点分治要找带权重心。
这种分治就是我们熟悉的树分治，代码难度减小了不少。
链剖分
UOJ 158
题意：给出仙人掌要求资磁 3 种操作：（1）一个点到根的最短路径上取反（2）一个点到根的最长路径上取反（3）子树内黑点个数询问。
树上肯定是树剖。仙人掌的话，我们可以对圆方树进行树剖。
考虑怎么支持我们的操作。首先由于要支持跳重链，我们必须能高效修改一整条重链上最长或最短路上的点。首先必须经过的点（即割点）肯定是要取反的，然而环上的点还得分类考虑，有时只要修改一部分点。
那么我们就可以把点进行分类。考虑每一条重链，将点分成 3 类：（1）割点（2）在重链上作为最短路径出现的点（3）在重链上作为最长路径出现的点。那么显然对于第 1 类点，直接在树上修改即可。然而对于后两种点，树上路径不一定会扫过需要更改的点。
我们考虑这样一个事情：在 DFS 序中，如果一个点是方点，那么我们先访问它的所有儿子，然后再按照重边先行的顺序访问儿子的子树（不包括那些儿子了），这样的话，我们修改一段区间的时候，就会扫过这个环上所有点；而我们已经把点分类了，因此也可以选择只修改最短路径或最长路径上的点。
那么这个问题就完美解决了。写起来比较码农，在进入重链时需要特殊处理。
鄂公网安备 42010202000505 号