概述
有用的点对？
例题
1.Tree Distance
点分治，记 $d_u$ 为 $u$ 到分治中心的距离，两点间的距离 $\le d_i + d_j$。
考虑对于每个点找到以其为 $d$ 最大值的点对。
对于 $i < j < k$，若 $d_i \ge d_j,d_k$ 那么 $(i,k)$ 会被 $(j,k)$ 完全包含。
先按编号排序，对于每个点找到前面/后面第一个 $d$ 比它小的点，组成点对。
总共 $O(n\log n)$ 个支配点对。询问相当于二维偏序，扫描线+线段树即可，时间复杂度 $O(n\log^2n)$。
2.[Ynoi2008] rdCcot
每个 C-块 取 bfs 序最小点作为代表元。
按编号排序，对每个点求出 $L_i,R_i$ 分别为其左右两边第一个 bfs 序比它小且能与它 C 连通的点。
询问 $[l,r]$ 的答案为 $\sum_{i=l}^{r} [L_i<l][r<R_i]$，扫描线解决。
对于 $L,R$ 的求解，由于与距离有关，用点分治，将子树节点按 bfs 序扫描线，线段树二分求出 $L_i,R_i$ 即可。
3.[Ynoi2003] 铃原露露
将节点编号按 $a$ 排序。若区间满足题面中 $[L,R]$ 的限制，那么它是合法的。对于 $(x,y,lca(x,y))$
若 $lca(x,y) \in [x,y]$ 无影响。
若 $lca(x,y)<x$ 那么区间 $[l,r] (l \in (lca(x,y),x],r \in [y,n])$ 是不合法的。
若 $y<lca(x,y)$ 那么区间 $[l,r] (l \in [1,x],r \in [y,lca(x,y)))$ 是不合法的。
相当于二维区间加，查询二维区间 $=0$ 的元素个数。
扫描线，线段树维护区间最小值及其个数，历史 $=0$ 的元素个数，查询区间历史和。
对于这种与 lca 有关的点对求解，一般用 dsu on tree 钦定 lca 求解。
对于特定的 $x$，取前驱后继作为 $y$ 即可，总共 $O(n\log n)$ 个支配点对。
时间复杂度 $O(n\log^2n)$。