BZOJ 1787/1832 [Ahoi2008]Meet

发布于 2017-05-08  202 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1787

                 http://www.lydsy.com/JudgeOnline/problem.php?id=1832

题意:一棵 n 个节点的树,m 个询问,对于每个询问,给出 x,y,z 三个点,确定一个点 P,三点到点 P 的距离和最小。


分类讨论一下,很容易发现 lca(x,y),lca(y,z),lca(x,z) 中至少有两个点重合,那么选择第三个点就是最优解

听说 lkhll 喜欢用链剖写 lca,稍微 yy 了一下,发现果然很好写,虽然复杂度是\(O(log_n^{2})\) 的,跑的却很快... 据说被证明常数小于\(\frac {1}{2}\)...

updata 2017/09/19 我是智障,复杂度显然是一个 log 啊。。。

于是代码如下:

 


一个非常弱的准退役OIER