圆方树

圆方树

这里的圆方树指广义圆方树。

对于一张 \(n\) 个点的无向图，其中包含 \(k\) 个点双，那么这张图建出的圆方树一共有 \(n+k\) 个点，其中前 \(n\) 个点为原图中的点，称为圆点，后 \(k\) 个点每个点代表一个点双，称为方点，每个点双与其中包含的点连边构成一个菊花，这 \(k\) 个菊花经由图中的割点连在一起。

圆方树的一些性质：

• 任取树上的一条链，其中圆点与方点交替出现。
• 两个圆点 \(u,v\) 在原图中简单路径的并等价于圆方树上 \(u,v\) 间的路径，且该路径上除 \(u,v\) 的圆点为 \(u,v\) 间路径的必经点。
• 顺带一提，除了两个点由一条边相连的情况，一个点双一定是一个边双。

在圆方树中，我们经常通过给每个点赋上恰当点权的方式解决问题。

例题：

铁人两项

枚举起点和终点，那么问题变为求这两点间简单路径点集的并，这等价于求圆方树上两点间间路径代表的点的并。

建立圆方树，给圆点赋 \(-1\) 的权，方点赋其代表的点双大小的权，那么点对 \(u,v\) 的答案就是圆方树上 \(u,v\) 路径的权值和。

Proof：首先我们记录了路径上所有点双大小的和，但这样会算重，因为两个点双间由同一个割点相连，给圆点赋值为 \(-1\) 恰好消掉了多算的一次。

然后换一种统计方式，树形 dp 求经过点 \(x\) 的路径条数在乘上这个点的权即可，注意图可能不连通。

Tourists

这题 *3200

要求所有简单路径上的最小值，那么我们可以建立圆方树，圆点的权值为它自己，方点的权值为与它相连的圆点的权值的最小值，树剖加线段树维护即可。

但是这样做一个圆点的修改会影响到若干个方点，所以我们将方点的权值改为它所有子节点的权值的最小值，这样修改时只需要改父亲即可。

注意这样做如果两点间 LCA 为方点的话还要算上它的父亲。

为了方便的修改权值，我们可以对每个点开一个 multiset，得以快速维护。

战略游戏

首先答案为点集中任取两点组成的点对间路径上圆点的并集大小，这个由圆方树的性质可以直接得到，所以设圆点的权值为 \(1\)，方点的权值为 \(0\)，求树上两点间权值和即可，但不应考虑两个端点。

但是这样做复杂度过高，考虑优化，类似于蓝书上异象石一题，将答案转化为包含集合中所有点的最小联通块，最终再减去集合的大小即可。

因此我们将这些点按照在树上的时间戳排序，然后依次统计相邻两点间的路径权值和，这里我们认为第一个点与最后一个点也相邻，这样一个点会算上两次，最后除 \(2\) 即可，但是这样不能统计第一个点与最后一个点的 LCA，最后要判一下。

Edge Queries

题目中的性质没有用，将题目中的简单路径转化为圆方树上两点间的路径，然后圆点权值为 \(0\)，方点的权值为它代表的点双内部的边数，因为一个点双中删一条边并不影响连通性。但要特判只有一条边的情况，此时不能删边。

如何统计点双中边的数量呢？我们可以对一个点双中的点先打上标记，然后枚举以这个点双中的点为起点的边，如果其终点也在这个点双中，那么经过这个点双的边数加一。但因为是无向图，所以最后的边数要除二。