参考资料
– 官方题解
– 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 循环那个数组的话会错。。
所以，最好在遍历树结束的同时把这些不用的信息都清理掉。。。
