由 Tarjan 衍生出来的一些东西

· · 算法·理论

本质：Tarjan 是通过忽略一些无用信息 来 简化结构。

Tarjan 大致分为两种：有向图和无向图。

Tarjan 可以对有向图或无向图进行缩点操作，也就是忽略环的内部结构。

dfs 树

无向图的 Tarjan 算法来自 dfs 树的性质。

性质：没有横叉边，所有非树边都是返祖边。

这是一个很强的性质，所以当我们面对无边权的无向图的生成树问题时，可以优先考虑 dfs 树。

P5811 [IOI 2019] 景点划分

显然数量越小就越容易连通，所以假设 a\leq b\leq c，且可以直接忽略 c 部分的求解，而且这样的话 a\leq \frac{n}{3}。

对于连通性问题，我们完全可以去考虑生成树，从而简化结构。

所以先思考对于树的情况，其实只要存在一条边，使得边两侧的子树大小分别 \geq a,b 就可以。

发现因为有 c 在容错，所以我们只需要找到一个子树大小在 [a,n-a] 内的即可。

那树和图的区别在哪？当找不到一个满足条件的子树时，可以通过非树边去调整子树大小。

因为有非树边的存在，且又是生成树问题，所以可以很自然地想到 dfs 树。

当且仅当存在一个子树大小大于 n-a 且其子节点的子树大小均小于 a 时不存在满足条件的子树，而 a\leq \frac{n}{3}，所以可以直接调整一整棵儿子子树，因为必定存在某时刻满足子树大小在 [\frac{n}{3},\frac{2n}{3}]（如果有解的话）。

所以无解的情况就是当调整完所有可以调整的儿子子树后，节点的子树大小依旧大于 n-a。

当然，Tarjan 还可以处理一些别的关于无向图的问题，这是本文要讲解的重点——点双。

点双的定义：任意两点之间至少有两条点不交的路径。

这里的点不交有两方面的指代：一是路径是简单路径，二是两条路径无交。

割点的定义：一个点属于多个点双。

点双有一些性质：

  1. 每条边恰好属于一个点双。
  2. 一条边是割边等价于所在点双大小为 2。
  3. 任意两点 x,y 之间的简单路径的并集为 x 到 y 路径上的所有点双。

正因为性质 3. 和点双的定义所以点双能够去处理两个之间简单路径的题目。

一种很有趣的理解方式，其实就是点双和边双的加边艺术：

例题：P5489 EntropyIncreaser 与 动态图。

圆方树

圆方树通常是和点双一起考虑的，也就是通过忽略点双的内部结构从而使无向图变为树。

也就是对于一个题目，链与环之间存在区别，但是环与环之间可以看作是相同的。

具体的说，圆方树是对于每个点双建立一个方点，方点连接点双中所有圆点，形成一个形似菊花图的东西。（注意：圆方树有时候会将大小为二的环也算作点双。）

所以圆方树一般的解题思路都是：在圆点考虑单点信息（此时忽略环的特殊性），在方点考虑整个点双的信息（此时再计算环的特殊性）。

圆方树有许多优秀的性质：

  1. 圆方树的形态不随根的变化而改变。
  2. 对于任意节点 x,y，x 到 y 的圆方树上路径上的非叶子圆点即为 x 到 y 路径上的割点。

所以就是建出圆方树的虚树，然后查找虚树上有多少个非叶子的圆点。

可以说圆方树是一种思想，你不一定会对每个点双的问题都建出圆方树，但是想思路的时候完全可以把问题放在圆方树上思考。

P3225 [HNOI2012] 矿场搭建

很显然是一个点双的问题，先建出圆方树，观察一下性质。

由于圆方树描述的就是删去一个圆点后的连通块，所以我们只要保证对于每个圆点的子树内部存在至少一个救援出口即可。

也就是每个叶子点双会被当做救援出口。

CF487E Tourists

结合点双的性质 3. ，其实求的就是 x\rightarrow y 路径上所有点双中点的最小值。

所以我们可以将点双中的所有圆点的信息全部挂在方点上，然后做树链剖分。

但因为有修改操作，导致一个圆点可能会对应多个方点，时间复杂度过不了。

圆方树其实还是一个树，而树最大的性质（也是与图的区别）就是在于树上节点只有一个父节点，所以我们可以只将圆点的信息挂在其父亲方点上，之后分类讨论即可。

CF1763F Edge Queries

可以发现题目前面给的性质可谓说是完全没有用处。

根据点双的性质 2.，一条边是割边等价于所在点双大小为 2，所以直接将方点的权值设为这个点双中边的大小，并且将点双边大小为 1 的权值设为 0。

然后再用 LCA 处理即可。

P4606 [SDOI2018] 战略游戏

根据圆方树的性质 2.，对于任意节点 x,y，x 到 y 的圆方树上路径上的非叶子圆点即为 x 到 y 路径上的割点。

所以就是建出圆方树的虚树，然后查找虚树上有多少个非叶子的圆点。

P4630 [APIO2018] 铁人两项

一个很经典的 trick：对于一个三元组 x,y,z，我们可以定一求二，而定住的显然是中间的 y。

所以现在就是要求对于每个节点，有多少条简单路径可以穿过它。

显然对于链和环是有区别的，在链中只有 x\rightarrow y \rightarrow z，但在环中任意一个组合都是可以的。

当然这个环指的是点双，而非边双，因为导致链和环产生区别的是环内部的任意点之间都有至少两条简单路径。

显然两条简单路径和多条简单路径的本质是相同的，所以下图中的两个环是没有任何区别的，也就是我们可以忽略环的内部结构。

所以可以建出圆方树，然后分别讨论圆点和方点的情况。

P8456 「SWTR-8」地地铁铁

显然可以正难则反，考虑什么时候 x,y 之间全是 D,d 的简单路径：

对于 1.，我们直接处理出每个点双是否是存在 d 或 D 的边，然后跑连通图即可。

对于 2.，显然在一个点双中最多只会有一对点产生这种情况，所以特判即可，而产生这种情况的条件就是当且仅当一个点双中只有两个点拥有不同颜色的出边。

仙人掌

一个仙人掌可以看作是一些简单环+一些边。

所以很多时候仙人掌问题都是：大致上当做树来处理，然后每个环内部的信息再单独处理。（环处理的时候很像基环树的思路，把每个点的贡献当作其子树的贡献。）

圆方树是处理仙人掌问题的利器，因为仙人掌每一条边至多属于一个简单环内，圆方树中点双的内部信息不会被忽略，边是一一对应的。

P4244 [SHOI2008] 仙人掌图 II

建立圆方树，分别考虑方点和圆点的情况。（其实就是分开考虑环和链。）

显然对于圆点，直接用树的思路去转移即可。

而对于方点，与圆点不同的是方点所对应的圆点也是可以互相连接的，对于圆点 i,j 所产生的贡献是 dis_i+dis_j+\min(len-i+j,i-j) ，那可以定一求一，然后显然可以通过限制 i-j 的取值来消掉 \min，然后就变成了单调队列的问题。

CF1893E Cacti Symphony

题目中的两个限制还是很强的，所以可以稍微推一推性质。

  1. 边的颜色必须是两端点中颜色之一（可以理解为是给边定向），且两个端点的颜色不同。
  2. 一个点所对应的边中与其颜色不同的边的数量必须为奇数。

可以发现因为这两个性质，题目可以完全被拆分为两个部分：

  1. 给边定向，使得每个点的出度为奇数。
  2. 给点染色，使得一条边的两个端点的颜色不同。

而最终的答案就是两者方案数的乘积。

对于 1. 来说，显然可以先找一些简单的东西，对于每个叶子节点显然其连边是定向的，那么如果是一棵树的话，那整棵树边的方向一定是定的。所以只用考虑环的方案数，而环显然有两种方案。所以最终答案就是 2^{cnt\_row}。

对于 2. 来说，还是分为树和环来考虑。因为观察到题目中的限制其实很少（因为只用考虑被加入的点两侧点的颜色），所以可以直接用 dp_i 表示大小为 i 的环的方案数，而 dp_{i+1}=dp_i+dp_{i-1}\times 2，最后数学归纳法得 dp_n=2^n+2\times (-1)^n。那么对于树来说，每一条树边都会使得方案数乘上 \frac{2}{3}。