题解 | #Genealogy in the trees#

感觉题解太智力了，写个不带脑子的大暴力 $O(qlog^2n mlogn)$ 做法。

给定 $m$ 个点对， $q$ 次询问，对每次询问的点对 $(a,b)$ 查询有多少点对 $(x_i,y_i)$ 满足 $x_i$ 是 $a$ 的祖先， $b$ 是 $y_i$ 的祖先。

树上问题考虑转换成序列问题，先转换到dfs序上。

考虑拆解查询，满足 $x_i$ 是 $a$ 的祖先这个条件在重链剖分之后是 $logn$ 段区间，满足 $b$ 是 $y_i$ 的祖先这个条件是一段连续区间，所以把一次询问拆成 $logn$ 次互不相交的询问最后相加即可。

现在问题转换成了，二维平面中有 $m$ 个点与 $qlogn$ 个矩形，求每个矩形覆盖了多少点。这是一个经典问题直接离线询问即可。通过一个简单的单点加，区间询问的线段树即可在 $O(qlog^2n mlogn)$ 时间内通过。

（赛时我的代码是拆 $m$ 个点，转化成矩阵加1，单点求值。但是本质相同。）