P5374 [THUPC2019]不用找的树

gxy001 · 2021-09-03 10:44:11 · 题解

首先你要会树分块，这种树分块满足每个块都是一个连通块，且每个块只有最多两个节点与其他块相连，更多内容不赘述，可以看我的博客。

一个邻域可以被拆分成不同块内的 O(B) 个邻域，其中只有 O(1) 个邻域的中心不是界点。

先对每个块单独处理，只考虑同一块内的两个邻域的贡献，分两种情况。

• 两个邻域的中心有至少一个不是界点，这种情况总共只有 O(m) 次。我们知道 d(a,b)=d(rt,a)+d(rt,b)-2d(rt,\operatorname{lca}(a,b))，我们只要知道 \sum d(rt,\operatorname{lca}(a,b)) 就可以了。对一个邻域内的点到根的路径全部加一，求另一个邻域内的每个点到根的路径的权值和就是我们要求得值，总时间复杂度 O(mB)。
• 两个邻域的中心都是界点，中心只有三种情况，半径只有 O(B^2) 种情况，所以总情况数只有 O(B^2) 种，预处理出来就行了，预处理的方法是枚举第一个邻域的半径，然后用上面的方法就可以求出第二个邻域所有半径下的答案，总复杂度 O(\frac {n}{B}B^2)=O(nB)。

在考虑不同块之间的贡献，对于两个不相交的邻域，有一个求出答案的方法，找到一个点使得从两个邻域中各选一个点路径必定经过这个点。只要求出每个邻域所有点到这个点的距离和点的个数，称为 d_i,c_i，则答案为 d_0c_1+d_1c_0。对每个询问每个块求出邻域在这个块内点的个数和到两个界点的距离和，在收缩树上按照这个式子 dp 一下子就完事了。

时间复杂度 O((n+m)\sqrt n)，空间复杂度 O(n+m)。

代码就不放了，需要的可以找我要。