思考如何将到 \(u\) 距离短的和到 \(v\) 距离短的节点分别处理出来。发现对于一次询问 \((u,v)\)，可以将所有节点分成三类：
-
除 \(u\) 和 \(v\) 的 LCA 的子树外的所有节点。
-
将 \(u\) 至 \(v\) 的最短路径的最中间的边删掉后组成的两棵树中的其中一棵树中的所有节点。
-
不属于以上两类节点的所有节点。
我们令 \((u,v)\) 深度较浅的点为 \(v\)，又令 \(v\) 属于第二类点，那么显然第一和第二类节点到 \(v\) 的距离更短，第三类点则是到 \(u\) 的距离更短。分类过程中找 LCA 和最中边都是 \(\mathcal{O}(\log n)\)。
我们发现三类节点将原树分解成三棵树，那么我们就在每棵树里找这棵树中的所有节点到 \(u\) 或 \(v\) 的距离，以此为这棵树的答案。因为我们分别把到 \(u\) 距离短和到 \(v\) 距离短的节点分类出来了，所以总答案即为三棵树的答案之和。上面找距离之和可以预处理 + 倍增，时间复杂度 \(\mathcal{O}(\log n)\)。
总时间复杂度：\(\mathcal{O}(m\log n)\)。
Code。