本题的理论做法其实很简单。对于位于不同子树的两个节点，计算出节点子树的大小，相乘即可。对于位于相同子树的节点，即节点A是节点B的祖先，我们需要对节点B的子树节数，并且需要对以A节点为根的子树减去B节点所在的子树的剩余部分计数。（看晕了吧，自己简单画一下就知道了）

所以本题的难点就在于求两个节点是否在同一个子树上，以及在同一个子树上的计数问题。

这两个问题一定要同时考虑，因为求两个节点在同一子树上的问题其实就是LCA（最近公共祖先）问题。而最近公共祖先有三种常见的解法：Tarjan（离线），倍增法（在线），RMQ（在线）。这三种方法中，只有倍增法记录了树上的路径，这对我们的计数非常用帮助。

倍增法的原理是这样的。对于每一个节点，我们都记录它的在树中的深度，然后用二分法向上枚举其公共祖先，进而找到最近公共祖先。向上枚举的过程可以通过预处理加速，我们记录每一个节点向上移动2^i步所到达的节点，这样每次枚举的时间复杂度是O(logn)。

预处理出移动到的节点的另一个好处在于计数。由于在计数中，我们需要将以A为根的子树中，将B所在的子树减去。此时，我们就可以从B节点向上走(depth_B - depth_A - 1)步，得到相应的节点后，减去该子树的节点数。就可以通过一个简单的乘法求出答案了。

所以本题就是LCA倍增法的一个经典应用。

请我喝一杯可乐

待字闺中微信群

内部测试期间，先加以下微信为好友，之后会把你拉入群中