搜 索

圆方树

  • 347阅读
  • 2021年10月08日
  • 0评论
首页 / 学习笔记 / 正文

仙人掌

任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。



对于某些问题,在树上很好做,但在图上就变得困难了起来。所以对于图,我们试图把他变成树,然后做一些树上可以做的东西(如虚仙人掌,点分治...)

DFS 树

对于一张图,我们任选一个根,然后 $\rm DFS$ 搜索得到一棵树,非树边连接的两个点只可能是儿子与祖先(即不会有横叉边)。对于一条非树边 $\rm (u,v) $ 我们称书上 $\rm u$ 到 $\rm v$ 的路径被 $\rm (u,v)$ 覆盖。

对于一棵仙人掌,非树边覆盖的区间两两不相交,即一条非树边对应一个环。所以很方便能知道每一条边属于哪个环

圆方树

那么圆方树是什么呢?

通俗地来讲,圆方树有两类点,圆点和方点。原图中每一个点都是一个圆点,而每个环对应一个方点(新添加的)。

如果原图一条边不属于任何一个环,那么直接添加进圆方树。而对于一个环,环代表的方点环上每一个点连边

圆方树就是这个样子

构建

构建圆方树,就像 $\rm Tarjan$ 缩点一样,然后把大小超过 $\rm 1$ 的环新建方点并连边,其余的边直接加进去就好了

性质

方点不会和方点连边

这个显然成立

无论取谁为根,圆方树形态不变,即圆方树是无根树

这个也显然吧,只是编号不一样而已

以 $\rm r$ 为根的仙人掌上 $x$ 的子仙人掌就是圆方树中 $\rm r$ 为根时, $\rm x$ 子树中的所有圆点

应用

有了圆方树后,我们就可以求解更多问题了!

仙人掌最大独立集

对于一棵树,我们记录 $\rm dp[i][j]$ 为节点 $\rm i$ 状态为 $\rm j$ 时候,最大独立集

但是仙人掌会有非树边,不好维护,怎么办。最经典的方法就是,我们对于不在环上的边,正常 $\rm dp$ ,对于一个环,我们把它单独提出来做一遍 $\rm dp$ 即可。

仙人掌直径

和普通树的直径一样 $\rm dp$ ,然后对于一个环单独拉出来单调队列做一下就好了

仙人掌两点最短路

上面两个都可以在 $\rm Tarjan$ 的过程中处理,而这个就需要构建圆方树了。但是怎么定义圆方树的权值呢?

对于圆圆边,我们还是原图的权值。对于圆方边,我们赋为这个圆点到环的顶端的最短路径长度。

于是对于询问 $\rm (u,v)$ 我们可以直接找到他的 $\rm lca$ ,如果 $\rm lca$ 是圆点,那么直接计算答案 $dep[x]+dep[y]-2dep[lca]$ , 如果是方点,我们找到 $\rm u,v$ 分别属于 $\rm lca$ 的儿子 $\rm su,sv$ ,答案就等于 $ dep[u]+dep[v]-dep[su]-dep[sy]+dis(su,sv)$ 其中 $\rm dis$ 表示最短距离。由于在环上,我们取两边最小值即可。

广义圆方树

我们思考能不能对于任意一张图都用圆方树来处理。答案是可以的。

我们对于每一个点双都构建一个方点,但是广义圆方树上,圆圆点也不能连边,怎么办呢?我们把两个点看成一个点双就好了!


应用

带修改,求无向图中两点之间所有简单路径上的最小权值

我们考虑不带修。如果走过一个点双,那么肯定有一种方法使得你走进点双,经过点双内权值最小的点然后出去。

然后,我们直接建立圆方树,方点权值就是点双内部最小值,树剖 + 线段树就可以处理

但是带修怎么办。修改一个点暴力遍历相邻方点的话,菊花图会直接 $\rm n^2$ 。于是我们考虑更改一个圆点,只需要更新他的父亲点(肯定是方点),更新的话用 $\rm multiset$ 即可。注意如果 $\rm lca$ 是方点,我们还要把他父亲的点计算进答案。

无标签
评论区
暂无评论
avatar