某岛

… : "…アッカリ~ン . .. . " .. .
March 19, 2020

UOJ 87. mx 的仙人掌

参考资料

官方题解
https://blog.bill.moe/uoj87-mxcactus/

题意

给定一个仙人掌,每次从中选取几个关键节点,求它们之间两两之间距离的最大值。

题解

对于树的情况,如果你只会虚树或者树分治,对于仙人掌你肯定也只能这么做了。
—— 官方题解

所以这个题乃会几种做法,取决于树的版本的那个问题,你会几种做法。官方题解 的六、七、八、九,提供了四种思路。这里先实现第一个算法 —— 虚仙人掌。

虚树

先当成树做,拿个 30 分再说。。。这里我用 f[] 数组记录向下的最长距离,然后在更新 f[u] 之前,先用 f[v] 和 f[u] 一起更新一下全局的直径,这样就不需要记录次大值了!

http://uoj.ac/submission/387435

虚仙人掌 (a.k.a. 圆方树)

首先对这类题目来说,通常的做法,是 dfs 的时候,找到环,然后再环上手工 dp 一次(但其实我总是敲错,需要依靠底力),把经过环的结果统计到答案,并更新到环上的根节点。
事实上对于 BZOJ 1023. [SHOI2008]cactus仙人掌图IOI 2008 D2T1 Islands 我们就是这样做的(分别是 直径 和 最长链,转移方程几乎一样)。

但我们发现并不是总能靠底力凹出来,比如 BZOJ 2125: 最短路,树上两点的最短路需要求 lca,仙人掌上怎么求 lca,似乎需要大量 if-else 判断 = =!!!
这个题的情况类似,因为在构建虚树的过程中,我们也需要求 lca。

这个时候我们就需要使用一种 常用的技巧 圆方树。参见 圆方树——处理仙人掌的利器

简单说来,圆方树就是把环边都去掉,新建一个 方点 来代替这个环,用环上的根节点连一条边到她,在从她到每个环上的其他节点连一条边,形成菊花形状以拆环为树(怎么样?是不是很像 block-cut tree)。

具体实作的话,先建三个结构体,分表表示 —— 原图,圆方树,虚树。分别记作 G,C,T。求圆方树的过程,可以类比 tarjan 求双联通分量,我这边是在最深的节点拉回反向边的时候,把环抠出来的(因而需要取个反)。
这里连向方点的权值为 0,而从方点连出的边的权值为左右两条路径的长度取 min。

紧接着在 C 上再 dfs 一次,预处理出 dp 和 lca 所需要的信息,为构造虚树做准备。最后求虚树的地方,和 之前写的代码 唯一的不同,是如果是从方点连出去的边,需要把这个环上连出去的那个孩子也加到树中,因为我们需要这些节点来正确处理环上的 DP。

void add_edge(int x, int y) {
if (x > G.n && x != C.fa[0][y]) { // 如果是从方点连出去,并且 y 不是连出去的那个孩子。
int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
adj[x].PB(z);
x = z;
}
adj[x].PB(y);
}

这个地方也是之前裸凹的时候最麻烦的地方,因为现在有了圆方树,所以几行就处理了掉了w。

接下来是下一个容易错的地方,以样例来说,在建立虚树的时候我们会把 2 和 9 所在的这个环也加到虚树里,而这个环本身的信息有可能会节外生枝,包含一些本不应该被考虑到节点(这里是 7),所以我们更新答案的时候干脆只用圆点的信息更新即可(上面 add_edge 里补上的节点并不会影响)。

参见 下图

最后说一个让我 wa 成傻逼的地方,就是最后的资源回收。。。因为这种虚树的题通常我们是不能无脑 memset 的,但是我们刚才构建虚树的时候,中间又加入了一些新的节点,所以直接 for 循环那个数组的话会错。。
所以,最好在遍历树结束的同时把这些不用的信息都清理掉。。。

http://uoj.ac/submission/387655