# 参考资料
– [官方题解]()
– [https://blog.bill.moe/uoj87-mxcactus/](https://blog.bill.moe/uoj87-mxcactus/)

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

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

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

## 虚树

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

<a href="http://uoj.ac/submission/387435">http://uoj.ac/submission/387435</a>

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

首先对这类题目来说，通常的做法，是 dfs 的时候，找到环，然后再环上手工 dp 一次（但其实我总是敲错，需要依靠底力），把经过环的结果统计到答案，并更新到环上的根节点。
事实上对于 [BZOJ 1023. [SHOI2008]cactus仙人掌图](http://www.shuizilong.com/house/archives/bzoj-1023-shoi2008cactus%e4%bb%99%e4%ba%ba%e6%8e%8c%e5%9b%be/) 和 [IOI 2008 D2T1 Islands](http://www.shuizilong.com/house/archives/ioi-2008-islands/) 我们就是这样做的（分别是 直径 和 最长链，转移方程几乎一样）。

但我们发现并不是总能靠底力凹出来，比如 [BZOJ 2125: 最短路](http://www.shuizilong.com/house/archives/bzoj-2125-%e6%9c%80%e7%9f%ad%e8%b7%af/)，树上两点的最短路需要求 lca，仙人掌上怎么求 lca，似乎需要大量 if-else 判断 = =！！！
这个题的情况类似，因为在构建虚树的过程中，我们也需要求 lca。

这个时候我们就需要使用一种 常用的技巧 圆方树。参见 [圆方树——处理仙人掌的利器](http://immortalco.blog.uoj.ac/blog/1955)。

简单说来，圆方树就是把环边都去掉，新建一个 方点 来代替这个环，用环上的根节点连一条边到她，在从她到每个环上的其他节点连一条边，形成菊花形状以拆环为树（怎么样？是不是很像 [block-cut tree](http://user.qzone.qq.com/251815992/blog/1582441616)）。

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

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

[cpp]
[/cpp]

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

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

参见 [下图](https://dreampuf.github.io/GraphvizOnline/#%0Agraph%20G%20%7B%0A%20%20%20%203%20--%208%20%5Blabel%3D7%5D%0A%20%20%20%201%20--%206%20%5Blabel%3D9%5D%0A%20%20%20%207%20--%202%20%5Blabel%3D10%5D%0A%20%20%20%208%20--%209%20%5Blabel%3D9%20color%3D%22red%22%5D%0A%20%20%20%201%20--%207%20%5Blabel%3D1%5D%0A%20%20%20%208%20--%205%20%5Blabel%3D2%5D%0A%20%20%20%204%20--%205%20%5Blabel%3D4%5D%0A%20%20%20%201%20--%207%20%5Blabel%3D4%5D%0A%20%20%20%202%20--%209%20%5Blabel%3D8%20color%3D%22red%22%5D%0A%20%20%20%209%20--%203%20%5Blabel%3D3%5D%0A%20%20%20%208%20--%204%20%5Blabel%3D2%20color%3D%22red%22%5D%0A%20%20%20%201%20--%206%20%5Blabel%3D5%5D%0A%20%20%20%207%20--%209%20%5Blabel%3D10%5D%0A%7D%0A%0Agraph%20G%20%7B%0A%20%20%20%203%20--%208%20%5Blabel%3D7%5D%0A%20%20%20%201%20--%206%20%5Blabel%3D9%5D%0A%20%20%20%207%20--%202%20%5Blabel%3D10%5D%0A%20%20%20%208%20--%209%20%5Blabel%3D9%5D%0A%20%20%20%201%20--%207%20%5Blabel%3D1%5D%0A%20%20%20%208%20--%205%20%5Blabel%3D2%5D%0A%20%20%20%204%20--%205%20%5Blabel%3D4%5D%0A%20%20%20%201%20--%207%20%5Blabel%3D4%5D%0A%20%20%20%202%20--%209%20%5Blabel%3D8%5D%0A%20%20%20%209%20--%203%20%5Blabel%3D3%5D%0A%20%20%20%208%20--%204%20%5Blabel%3D2%5D%0A%20%20%20%201%20--%206%20%5Blabel%3D5%5D%0A%20%20%20%207%20--%209%20%5Blabel%3D10%5D%0A%7D)。

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

<a href="http://uoj.ac/submission/387655">http://uoj.ac/submission/387655</a>