UOJ Logo immortalCO的博客

博客

共找到 1 篇包含 “仙人掌” 标签的博客:

圆方树——处理仙人掌的利器

2016-08-01 09:11:36 By immortalCO

营员交流课件

链接: http://pan.baidu.com/s/1hrM1Ic8 密码: dc4j

概述

随着业界毒瘤的推动,我们开始见到越来越多的仙人掌题。对于这种题,我们总是想办法把仙人掌转化为树来做,从而将熟悉的树的算法修改后用于仙人掌上。

圆方树是一种由我们提出的树的结构,它能轻松的将仙人掌转化为树,并能资磁仙人掌上点分治、虚仙人掌、仙人掌剖分等经典的树上问题,在 UOJ 上若干道仙人掌题目中,均有极高的效率。

构造

首先我们要构造原仙人掌 $G$ 的圆方树 $T_G$。我们定义原仙人掌上的点为圆点,现在我们考虑转化。

我们对仙人掌进行点双的 Tarjan 算法,因为仙人掌上每个环都是一个点双,而且在栈中的顺序就是环上点的顺序。那么考虑一个点 $i$ 的一条出边 $(i,j)$ 满足 $dfn(i) < low(j)$,那么说明 $(i, j)$ 是一条树边,我们在 $T_G$ 中直接连上这两个点即可;如果 $dfn(i) = low(j)$,那么我们找到了一个环(可能是重边造成的二元环),则从栈中取出点直到取出 $j$ 为止,设这样从栈中取出的点集为 $R$,则 $R \cup \{i\}$ 是一个环;对于其他情况,我们按照 Tarjan 的步骤执行即可,无需特殊处理。

对于一个环 $R \cup \{i\}$,设 $i$ 为环的 。我们新建一个方点 $P$,在 $T_G$ 中连接所有的 $(P, q), q\in R \cup \{i\}$。这样连的边数等于环上点数,而点又多了一个,因此最后连出的 $T_G$ 是树。

性质

圆方树有优美的性质。

  1. 无论如何换根,圆方树形态不变 //因为你是把环连成菊花而不是别的什么

  2. 圆方树的子树 = 原仙人掌的子仙人掌 //分类讨论各种情况可以证明

  3. 方点不会和方点相连

还有其他神奇的性质,要具体题目具体分析。

应用

最短路

类比树上最短路,我们在 LCA 处考虑。然而圆方树的树上距离并不一定就等于仙人掌上的最短路长度。

注意到圆方树中的边权都还没有确定,那么我们就可以现在确定了。如果一条边是圆圆边(圆点指向圆点的边,这里已经任意选择一圆点为根),那么它是一个树边,边权等于原仙人掌上边权;如果是方圆边,那么边权等于环的根到那个圆点的最短路径长度;如果是圆方边,那么边权为 0。

这样,如果一对询问点在圆方树上的 LCA 是圆点,那么其圆方树上长度就是原仙人掌上长度,因为路径上唯一的不同就在于对于每个环是走哪一侧(这个决策对每个环是独立的),而前面边权的确定已经解决了这一问题;如果 LCA 是方点,则我们只需要考虑在 LCA 这个环中是否要走经过根的那一侧。我们需要找出这两个询问点 $(x, y)$ 分别是在这个方点的哪两个儿子 $(p_x, p_y)$ 的子树中(这就是个 jump 操作,可以用倍增或树链剖分轻松实现)。则 $x \rightarrow p_x$ 和 $p_y \rightarrow y$ 的树上距离都是最短路径,现在就只需要考虑同一个环上的点 $(p_x, p_y)$ 的最短路径(其实也就是走哪一侧的问题)。 前面先记录环上边权的前缀和,这样就能 $O(1)$ 计算出不经过根那条路径的长度,再通过记录整个环的边权和比较出走哪一侧更优。

例题:http://www.lydsy.com/JudgeOnline/problem.php?id=2125

DP

仙人掌有若干种 DP,比如最大独立集和直径。

最大独立集比较简单,只需要 DFS 时,树边按照树上独立集的方式转移,环上用一个 $f(i, 0..1, 0..1)$ 的简单 DP 去转移即可。

例题:http://www.lydsy.com/JudgeOnline/problem.php?id=4316

求直径的话,我们类比求树直径的方式,在 LCA 处考虑。设 $f(i, j \in {1,2})$ 为 $i$ 子树中的第 $j$ 深的点,那么圆点可以轻松转移、更新答案。在方点转移也容易,但更新答案不能直接更新(因为有哪一侧的问题,直接取不一定是最短路,会导致答案偏大)。我们可以把环复制一份用单调队列来解决,也可以正反各做一次前缀和。

例题:http://www.lydsy.com/JudgeOnline/problem.php?id=1023

虚仙人掌

对一个点集的子集进行询问。分例题进行讲解。

UOJ 87

http://uoj.ac/problem/87

题意:给出一个点集,求点集中两两最短路径的最大值。

首先对原仙人掌建立 BZOJ 2125 那种带边权的圆方树。然后每次对圆方树建立虚树,在虚树上按照 BZOJ 1023 的方法进行简单 DP 即可。

UOJ 189

http://uoj.ac/problem/189

题意:给出仙人掌,要求资磁:(1)询问若干条最短、最长路径的并的边权和 (2)修改边权

先对所有端点的点建立圆方树的虚树。现在我们要考虑两部分的贡献:(1)对于虚树上一条边,对应圆方树上一条链,我们要一起考虑这条链的贡献;(2)对于虚树上的一个方点,对应一个环,我们要考虑它有哪几段计入答案。

我们对于每条边这么操作:首先找到 LCA,判断出是哪一段符合要求(最长或最短),然后像求圆的周长(某些计算几何题)那样记录两个括号用来扫描线;然后找出不在环上的一段(如果 LCA 是方点,要利用 jump 操作求出 $p_x, p_y$),利用子树前缀和的思想记录一下是否存在最长、最短路的询问(也就是在 $x$ 处 $+1$,在 $p_x$ 处 $-1$,然后一个点的权值为其子树中的权值之和)。

那么对于一条虚树上的边,我们就有 4 种情况,表示最长路和最短路分别是否有。我们可以通过一种特殊的“深度”来计算这些值。设 $f(i)$ 为从圆方树根到 $i$ 的树边长度之和,$g(i)$ 为从根到 $i$ 的最短路径,$h(i)$ 为从根到 $i$ 的最长路径。那么如果经过边$(i, j)$的又有最长路径又有最短路径,则贡献为 $g(j) + h(j) - f(j) - (g(i) + h(i) - f(i))$;如果只有最短路径则贡献为 $g(i) - g(j)$,只有最长路径贡献为 $h(i) - h(j)$。

环上的情况,我们像求圆上周长那样,对之前添加的括号排个序即可。

如果要修改,那么既有可能影响环上距离,又有可能影响那 3 种深度。我们分别用树状数组维护均可。注意如果修改的是环上的边,那么影响的深度数组到底是哪几段需要分类讨论。

点分治

UOJ 23

http://uoj.ac/problem/23

题意:求出仙人掌上从 1 出发长度为 $[1..n]$ 的简单路径的条数。

暴力是用背包的思想,设 $f(i, j)$ 表示从 $i$ 出发往下走 $j$ 步的路径条数。注意到转移是卷积的形式,那么我们可以用 FFT 来解决这一问题。

进行点分治。设当前子树中重心为 $G$,考虑求出 $f(G)$ 为这棵子树的背包数组。首先 $G$ 的包含当前连通块最高点(记为 $top(G)$)这一分支可以递归去做。现在考虑 $G$ 的儿子们,如果 $G$ 是圆点,那么直接把出边的 $f$ 加起来求和即可;否则如果是方点,那么每个儿子都有两种选择:向左或向右,两种情况都要加上去。现在还需要考虑 $top(G)$ 到 $G$ 这一段对 $G$ 出边贡献的 $f$ 的影响。显然我们可以再套一个分治 FFT 把 $top(G)$ 到 $G$ 这一条链上的数组算出来,但这样太笨了。我们维护 $g(G)$ 表示 $top(G)$ 到 $G$ 这一段的背包数组,那么我们发现从 $fa(G)$ 开始一直跳 $top$,一段一段跳上去,不会超过 $\log(top(G)\ 到\ G\ 的链长)$ 段,而且后一段的 $g$ 数组长度是前一段的两倍。这样暴力 FFT 卷积起来,复杂度只有 $top(G)\ 到\ G\ 的链长 \times \log(top(G)\ 到\ G\ 的链长)$,那么这个问题就在 $O(n \log^2 n)$ 的时间内完美解决。

一个细节是设方点点权为环的大小,点分治要找带权重心。

这种分治就是我们熟悉的树分治,代码难度减小了不少。

链剖分

UOJ 158

http://uoj.ac/problem/158

题意:给出仙人掌要求资磁 3 种操作:(1)一个点到根的最短路径上取反(2)一个点到根的最长路径上取反(3)子树内黑点个数询问。

树上肯定是树剖。仙人掌的话,我们可以对圆方树进行树剖。

考虑怎么支持我们的操作。首先由于要支持跳重链,我们必须能高效修改一整条重链上最长或最短路上的点。首先必须经过的点(即割点)肯定是要取反的,然而环上的点还得分类考虑,有时只要修改一部分点。

那么我们就可以把点进行分类。考虑每一条重链,将点分成 3 类:(1)割点(2)在重链上作为最短路径出现的点(3)在重链上作为最长路径出现的点。那么显然对于第 1 类点,直接在树上修改即可。然而对于后两种点,树上路径不一定会扫过需要更改的点。

我们考虑这样一个事情:在 DFS 序中,如果一个点是方点,那么我们先访问它的所有儿子,然后再按照重边先行的顺序访问儿子的子树(不包括那些儿子了),这样的话,我们修改一段区间的时候,就会扫过这个环上所有点;而我们已经把点分类了,因此也可以选择只修改最短路径或最长路径上的点。

那么这个问题就完美解决了。写起来比较码农,在进入重链时需要特殊处理。