圆方树学习笔记 ForgotMe · 2024-11-07 17:03:15 · 算法·理论 前言 其实本身是非常惧怕这个东西的。在我 oi 生涯的最后一年，虽然春测 CE 已经决定败……
圆方树学习笔记
ForgotMe
·
2024-11-07 17:03:15
·
算法·理论
前言
其实本身是非常惧怕这个东西的。在我 oi 生涯的最后一年，虽然春测 CE 已经决定败局，省选的 day1t2 突然出现的点双题目直接击溃了我，依然记得场上的绝望，只会最简单的爆搜。
广义圆方树是刻画无向图上点必经性的强力工具，是用于解决仙人掌上问题的圆方树的扩展，以下简称 圆方树（Block Forest）。它是点双缩点的产物，描述了原图任意两点之间的所有割点，即 u,v 之间的所有必经点。
圆方树最重要的一个点就是方点本身刻画了一个点双。点双之所以比边双难刻画是因为极大点双连通分量之间是有交集的，也就是所谓的割点，所以处理起来会更加麻烦。
一些圆方树的性质：
圆点 x 的度数等于包含它的点双个数。
方点 x 的度数等于它对应的点双大小。
圆点 x 不是叶子当且仅当它是原图的割点。
圆方树上圆方点相间。
连通无向图的圆方树连通（相邻两点点双连通）。
原图的每个连通分量对应一棵连通的圆方树。
[省选联考 2023] 城市建造
时隔两年，我又回来了。
其实并没有想象中的难。
题目本质上是要选择一个点集 V，把 V 中的导出子图的边删去后恰好形成 |V| 个连通块（该说法等价于删去后这 V 个点两两不连通）。
考虑一个关键性质：如果 u,v 同时被选入点集，那么 u\sim v 的所有简单路径上的点都应该被选，否则一定不合法。
这个性质跟点双中的一个关键性质恰好对应：对应一个点双中的三个点 u,v,w，一定存在一条简单路径满足 u\rightarrow v\rightarrow w，说明一个点双里的点要么选一个，要么全选。
下面证明这个问题可以转化为：建出圆方树，删去一些方点，要求删去的方点形成一个连通块，且使得剩下的连通块两两大小（连通块大小只算圆点）绝对值之差 \le k。
证明：首先先看只选一个圆点的情况，这种情况一定是不合法的，因为删去该点后要么原图依旧连通要么形成 \ge 2 个连通块。考虑选了 \ge 2 个圆点的情况，不断应用最开始推出的关键性质，可以发现对于选择的圆点 u,v，u\sim v 路径上所有的点双包含的点全部应该被选择，于是可以转化为直接删去方点。
那么转化后的问题就比较好做了。先看 K=0。
考虑枚举连通块大小 t(t|n)。
设 dp_x 表示：
强制圆点 x 的 father delete 的条件下，圆点 x 的子树中至少有一个方点 delete 且自身以点 x 为根的连通块大小为 t 的方案数。
方点 x delete 后子树 x 合法的方案数。
方点的转移是容易的，主要看圆点的转移，这个转移比较麻烦，本质上是要选择一些子树保留下来与这个圆点一起凑出来 t。注意到一个关键性质：一个大小为 sz 的子树，如果 sz 再看 K=1，这个要麻烦一点，同样可以枚举连通块大小，注意到可能的连通块大小种数只有 \sqrt{n} 种。方点的转移依旧不变，对于圆点的转移需要分类讨论，如果要求点 x 的连通块大小为 t，那么转移同上，如果为 t+1，那么会多出一种情况就是选择一个大小为 t 的子树，其他全部扔掉，这个可以通过前缀/后缀积优化算出来。 能不能更给力一点啊？注意到如果设 f_{u,d} 表示在点 u 且要求连通块大小的限制为 d 的方案数，那么所有有值的位置总和不超过 n。这个很容易观察出来，K=0 时就只有子树从小到大排序后其前缀和的地方可能有值。采用 hash 即可。 「SWTR-8」地地铁铁 非常棒的推结论题。 首先先建出圆方树，对于不在一个点双的点对是简单的，只要其路径的所有方点含有两种边即可。主要是在一个点对里的情况，正着想非常难。正难则反，考虑不存在一条路径同时都存在的特征，发现此时把 d 边删了会形成一些孤立点，把 D 边删了也会形成一些孤立点（注：孤立点不考虑起点终点），且两种情况下孤立点的并集是除了起点终点的集合。于是可以直接猜出结论：如果除了起点终点其他都是孤立点，那么不合法，否则一定存在一条合法的路径。于是直接计算孤立点的数量，当有两个点不是孤立点时，此时方案数是 \binom{sz}{2}-1，否则所有点对都合法（存在三个及以上的点不是孤立点）。直接计算即可，复杂度线性。 [APIO2018] 铁人两项 一个经典结论是 u 到 v 所有简单路径的并就是圆方树上两点经过的所有方点对应点双的并。那么这个题就随便统计一下就做完了。 CF1763F Edge Queries 题里给的条件完全没有用。 直接建出圆方树，根据上一题的结论，所有简单路径的并就是圆方树上两点经过的所有方点对应点双的并，边也是一样的，如果经过的点双是两点一边，说明这个边是割边，不计入答案即可。 [ZJOI2022] 简单题 答辩题。完全不想写。 首先先建出圆方树，那么从 u 到 v 的简单路径可以看做若干个 圆点-方点-圆点 路径的拼接，那么只需要解决其在一个点双中的子问题即可。对于一般图，这个问题是 NP 的，考虑题中给出的性质。可以推出这个图是一个杏仁，就是可以找出两个点 S,T，该点双就是若干条从 S 到 T 且点不交（除了起点终点）的路径。那么就好做了，直接对于每个点双分类讨论即可。 https://www.luogu.com.cn/record/189543253 基本对着第二篇题解的代码写的，这老哥的代码写的太优美了，大大的好！！