题目地址

http://uoj.ac/problem/87

算法一

估计大家应该不会被仙人掌吓到而直接$\mathrm{gg}$了，至少先会考虑任意图的情况。

妈妈我不会处理图的问题怎么办？

有$5\mathrm{\%}$的数据$n\le 7,\mathrm{tot}\le 7$，可以用各种方法(如枚举所有路径)水过去。

算法二

有$10\mathrm{\%}$的数据$n,\mathrm{tot}\le 5000$。

最短路算法

由于时限和数据都很令人感动，这些数据其实用$\mathrm{dijkstra}$甚至$\mathrm{SPFA}$(我多良心没有卡哦！(大雾))都能跑得过去......

更好的做法

考虑仙人掌图的$\mathrm{dfs}$遍历树，有很多条前向边，每条前向边$x\to y$对应一个环，不妨设这个环的根为$y$，每当我们找到一条前向边$x\to y$时，通过从$x$不断回到$\mathrm{dfs}$树上的父亲直到到达$y$，我们可以取出这个环上所有点，并且容易得出环的长度，对所有点除了$y$以外的点都标记一下它所在的环编号。

$\mathrm{dfs}$完以后，对每个点考虑他到根的距离，如果他没有环标记那么距离就是父亲到根的距离加上自己到父亲的边的长度。否则就是他到环的根$y$的两条路径长度(一个是$\mathrm{dfs}$树上的距离(这个用两个点离根的距离减一减就求出来了)，另一个是环的长度减去树上距离)中的较小值加上$y$到根的距离。

对每个询问的每个询问点，我们都遍历一遍，时间复杂度为$O(n\times \mathrm{tot})$。

算法三

有$10\mathrm{\%}$的数据$Q\le 10$。我们考虑对每一次询问直接$\mathrm{dfs}$一遍求得答案。

用${\mathrm{maxlen}}_x$表示从$x$出发到以$x$为根的子仙人掌(即在原图中删去$x$之后不与根相连的点和$x$的导出子图)的某个询问点的最短路的最大值(如果没有询问点可以设为-∞)，对于$x$的某个$\mathrm{dfs}$树上的孩子$y$，如果从$x\to y$的边$e$是割边那么就直接用${\mathrm{maxlen}}_y+w_e$更新${\mathrm{maxlen}}_x$，$w_e$表示$e$的权值，否则如果$x$成为了边$e$所在环的根那么我们要把环取出来，直接枚举换上的点然后用他的$\mathrm{maxlen}$加上他到$x$的两条路径长度的最小值更新$\mathrm{maxlen}$即可。

考虑更新答案，所有询问点的$\mathrm{maxlen}$显然可以用来更新答案，对一个点的两个不同的子仙人掌（即在原图中删去$x$之后不与根相连的点的一个连通块和$x$的导出子图)，他们的$\mathrm{maxlen}$之和加显然也可以用来更新答案(求出一个子仙人掌$y$的${\mathrm{maxlen}}_y$之后，先用${\mathrm{maxlen}}_y+{\mathrm{maxlen}}_x$更新答案，再用${\mathrm{maxlen}}_y$更新${\mathrm{maxlen}}_x$即可)。现在还需要考虑经过一个环的路径的情况。

经过一个环的最短路径一定是由两条环以外的路径(可以长度为0)和一条环上的路径组成，我们按顺序取出环上的边，并且复制一份接在后面，形成一条链。对于链上的点$i$，记$mathrm{len}_i$为链的头部到它的路径的长度，${\mathrm{val}}_i$为它对应的点的$\mathrm{maxlen}$，那么经过这个环的最长的最短路径即为$\max \{{\mathrm{val}}_i+{\mathrm{val}}_j+{\mathrm{len}}_i-{\mathrm{len}}_j\}(0\le {\mathrm{len}}_i-{\mathrm{len}}_j\le \frac{\mathrm{cirlen}}{2})$，其中$cirlen$表示该环的长度，容易用单调队列维护，时间复杂度为$O(Qn)$，如果用线段树时间复杂度为$O(Qn\log n)$。

算法四

对于树的情况，可以使用虚树。

虚树的建立方法之一是，对询问点按$\mathrm{dfs}$序排序，然后取出他们相邻节点间的$\mathrm{lca}$，接着再按$\mathrm{dfs}$序排序，接着扫一遍，维护一个栈，如果当前栈顶的节点是当前节点的祖先那么就连一条边，边权为它们之间的距离，否则将栈顶的节点弹出栈。这只是一种建立方法。

然后在虚树上$\mathrm{DP}$即可。

时空复杂度均为$O(n\log n)$(今后视tot = $O(n)$)

此外时间复杂度可以通过更大的代码复杂度降为$O(n\alpha (n))$或者$O(n)$，具体不再赘述，我多良心没有要求大家写这些算法哦！(大雾)。

算法五

对于树的情况，还可以用树分治解决。

一种较方便的树分治的做法是，先建立好树分治结构，然后对每一个询问，先将点去重。接着对于每一个树分治结构中的节点(对应一棵子树$T$)，我们只考虑该询问中所有在$T$中的点。直接用两个属于不同子树的点到根的距离和的最大值更新答案即可(要注意判一下询问点是根的情况)。接着对于它的每一个孩子节点，递归处理下去，注意我们只要保留该询问中在这个孩子节点中的点。

但是这个做法由于要预先存储结构，时间空间常数都比较大。

还有一种做法是，询问和树一起分治，这个很好理解，无非就是把两个过程合并了，每一次要处理的是一棵子树和一个询问序列，这个序列只保留所有存在询问点在该子树中的询问，并且每个询问只保留在该子树中的询问点，然后处理询问的方法如同前面所述。

时空复杂度均为$O(n\log n)$。

UPD:树上迭代两次求最远点即可，最远点可以直接枚举然后$\mathrm{lca}$，呜呜呜我出题的时候怎么就脑抽了，30分送大家吧，前面的算法就当做口胡......

算法六

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

如果我们能建立“虚仙人掌”，肯定可以解决这个问题。

我们想一想就能想清楚虚仙人掌的一种最笨但是也绝对正确并且可以通过这题的建立方法，先按$\mathrm{dfs}$序排序，再求出相邻节点间的$\mathrm{lca}$(注意这里$\mathrm{dfs}$序和$\mathrm{lca}$都是在它的$\mathrm{dfs}$遍历树上做，后面的深度也是)，接着我们取出每一个点所在环的根和环上最深的点，再排序并取一遍相邻节点$\mathrm{lca}$，然后建出$\mathrm{dfs}$树上的虚树，接着再每个环的最浅的点和最深的点之间连边，边权为它们原先连的边的权值(它们原先显然一定连了边)，由于我们要求的是最短路径，其实这里连它们之间在环上走的两条路径的较小值也没有关系，不会对任何最短路径造成影响，这一个画一画图就知道了。

根据上述结论，连虚树上的边时，可以将虚仙人掌上的环边和树边一视同仁，统统连它们两个端点在原仙人掌上的最短路径长度。但是这个最短路径长度和树上不同，树上可以直接用离根的距离减一减，仙人掌上就不是这么简单了，离根的最短路长度不具有可减性。是，我们可以用动态仙人掌。但是这样代码复杂度太高。我们考虑一下，如果树上有一个值也不具有可减性，比如路径边权最小值，你会怎么弄？一种方法就是倍增。对仙人掌也这么弄，考虑动态仙人掌维护生成树法的思想，我们记录每个点到它第$2^i$级祖先的最短路长度，同时如果有一个环不完全包含这条路径，且包含第$2^i$级祖先的父亲(显然这个祖先如果是根就不可能存在满足条件的环)，那么我们就记录一下这条路径上深度最大的在这个环上的点，合并的时候就根据这个环是走树边还是走非树边来求出最短路，非常简单。

UPD:好像可以记录到根的距离，然后用特殊的方法处理一下就可以直接减了。总之实现上有各种技巧优化时间复杂度和代码复杂度，感觉标程就是个逗比啊TAT......

实际上，std的方法和上述方法有细节上的差异，如果$x$本身连了一条非树边，包含了整个路径及$2^i$级祖先的父亲，那么他也将被记录，但是这样合并的时候将会多出一些小麻烦，因为一个环可能会更新一条路径两次，用后一次更新覆盖掉前一次更新即可。但是如果不用这个方法，$\mathrm{dfs}$树的叶子节点连接的非树边也要特判。不过这些东西都是一些细节问题，稍微处理一下即可。

总之这个算法可以非常愉悦的跑出100分， 时空复杂度均为$O(n\log n)。$

提交记录在这里。

算法七

对于树分治，我们显然也可以想办法把它搞到仙人掌上，也就是用仙人掌分治来解决问题，实现细节和树分治大同小异，每一次去掉一个点时，先把它弄成仙人掌的根，然后断开它连的所有割边，以及所有它所在环的环边，每一次选一个进行上述操作后，剩下来的子仙人掌中大小最大的最小的点来分治即可(其实为了方便我写的程序不一定能取出最小，但绝对剩下来的子仙人掌中大小最大的不超过$\frac{n}{2}$)。

处理每个询问时，根可能连着不少的环。对一个点（除了根），如果在某一个环$C$上或者某一个在$C$上的点(除了根)的子仙人掌，那么称这个点属于环$C$。，直接用两个属于不同子仙人掌或者环的点到根的距离和的最大值更新答案即可(同样要注意判一下询问点是根的情况)。但是我们还要注意属于同一个环但不是环上同一个点的子仙人掌的点，他们两两之间也要更新答案，这个用单调队列很好解决。

时空复杂度均为$O(n\log n)$。

解法八

松爷给出了另外一种解法，详见http://wangyisong1996.is-programmer.com/user_files/wangyisong1996/File/zjoi2015/cactus-slides/wys-cactus-slides.html#/6

AC代码：

http://uoj.ac/submission/13387

http://uoj.ac/submission/13388

第一份的空间复杂度是$O(n\log n)$，比第二份多一个$O(\log n)$，但代码量更小。

此外，仙人掌分治和虚仙人掌都可以在线，前者在线情况应该会TLE甚至可能MLE(至少我的写法如此= =b)，后者本身就可以在线。这种做法就没什么简单办法做到在线了= =b。

解法九

waltz给出了另外一种解法：http://uoj.ac/submission/13649

时间空间代码量都完虐我啊orz......

这个做法是对每个环，新建一个点，向环上每个点连长度为它到环的根的最短路径长度的边，如果对新树dfs，那么每个点到它的任意非新建祖先的最短路径长度就是它们之间在树上的距离，对于lca不是新建点的两个点最短路长度就是它们之间在树上的距离，是新建点的话，在树上的距离也不会小于真实距离，但我们可以单独取出环再单调队列来解决环的问题。这道题成功降级为符合人民大众胃口的既无思考难度也无代码难度的傻逼题。跪烂waltz！

基于这个思路，也许很多仙人掌上问题可能会有更简单的做法？

乱搞

我们发现对于树的情况，直径就是任取一个点$a$，求出他的最远点$x$，再求出最远点$y$，$x$到$y$的距离，应用到仙人掌上是不正确的。因为一个大环连上一条小边，只有$a$取到$O(1)$个点时才能求出答案，对于其他点就算不断找最远点迭代∞次答案也不正确。(想知道这个算法能拿多少分吗？写写就知道！)

另外我们还可以多次枚举点做根，然后设法求得经过根的最长路径，由于答案路径可能很长，一旦取到了一个答案路径上的点做根就可以求出正确答案。但是一旦答案路径比较短，这个算法就不靠谱了。并且这个算法没法较好的判断是否已经是当前答案已经正确。

如果你通过各种方法乱搞过了，你就可以好好感受一下$\mathrm{extra}\mathrm{test}$和$\mathrm{hack}$的威力了。

后记

其实这个题如果出成每对点的最短距离和的话，是可以避免乱搞的，而且不难实现，但是由于奇怪的原因，我没有把它改成这样。

在出题人想出一个原始的算法之后，算法又其他人不断被改进，长江后浪推前浪。感觉我从这道题的出题经历中感受到了科技的进步。

5s的时限真是太良心了233，主要是为了欢迎各种奇葩做法。