圆方树学习笔记

· · 算法·理论

介绍

边双缩点得到树，强连通缩点得到 DAG，而点双与之对应的就是圆方树。

我们这里将点双定义为不存在割点的图，在点数 > 2 的时候等价等价于任意两点间存在点不重合的两条路径。

单点不定义是否为点双，根据题意特判。

在圆方树中我们有圆点和方点，原点对应原图的点，而方点对应原图的点双。如果原图中一个点属于某个点双，那么在圆方树中，对应的圆点就连接对应的方点。

建树

与割点的求法几乎一致，在求点双的过程中加上连边操作即可。

判断是一个点 u 是割点：

  1. 存在儿子 v，low_v \ge dfn_u。

例题

P4630 [APIO2018] 铁人两项

我们先考虑固定 s,f，那么 c 的数量就是两点间简单路径的并的大小。

OBS：若 a,b,c 位于同一个点双，则存在一条简单路径：a\rightarrow b\rightarrow c。证明不难。

建出圆方树后一目了然。

一个类似点边容斥的技巧：将方点权值赋为点双大小，圆点权值赋为 -1。

答案就为两两圆点之间的权值和，容易计算。

固定 c 统计 s,f 应该也是能做的。