圆方树学习笔记

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

我们这里将点双定义为不存在割点的图，在点数

> 2

的时候等价等价于任意两点间存在点不重合的两条路径。

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

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

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

判断是一个点 $u$ 是割点：

例题

我们先考虑固定

s,f

，那么

c

的数量就是两点间简单路径的并的大小。

OBS：若

a,b,c

位于同一个点双，则存在一条简单路径：

a\rightarrow b\rightarrow c

。证明不难。

建出圆方树后一目了然。

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

-1

。

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

固定

c

统计

s,f

应该也是能做的。