给定一棵大小为 \(n\) 的树和 \(m\) 条链 \(s_i, t_i\)，询问有多少对 \((u, v)\) 满足 \(u, v\) 同时在一条链上？
\(n, m \le 10^5\)
一个十分暴力的做法：把一条链剖成 \(\log n\) 个区间，那么这 \(\log n\) 个区间两两都是有贡献的，得到 \(\log^2n\) 个矩形，每个矩形内的点对都是有贡献的。然后对 \(m \log ^2 n\) 个区间做矩形并即可，时间复杂度：\(O(m \log ^3n)\)。
但是这个做法太暴力了，考虑只有一维还是拆成 \(\log n\) 个区间，另一维存若干条链（区间内的点和链上的点有贡献）。对于每个点 \(u\)，它的贡献就是这若干条链的并，因为它们都经过点 \(u\)，用个 set 维护下端点，按 dfs 序排序后求相邻两个点的距离，再除以 \(2\) 即可。（经典套路。）
时间复杂度是两个 log 的。