Take an arbitrary root to regard it as a rooted tree. Let \(dep_v\) be the depth (distance from the root) of \(v\), and \(sz_v\) be the number of vertices in the subtree rooted at \(v\).
With an appropriate precomputation, how can we answer the queries fast enough? Given integers \(L\) and \(R\), we find the answer.
Assume \(dep_L < dep_R\) by swapping them if necessary. We want to find the sum of \(\min(d(j,L), d(j,R))\), so we now compare \(d(j,L)\) and \(d(j,R)\).
Let \(M\) be the vertex resulting from traversing edges \(\lfloor \frac{(d(L,R)-1)}{2} \rfloor\) times toward the root; then, since \(dep_L < dep_R\), \(M\) is a descendant of the LCA (Lowest Common Ancestor) of \(L\) and \(R\), so vertex \(j\) satisfies \(d(j,L) > d(j,R)\) if \(j\) is in the subtree rooted at \(M\), and \(d(j,L) \leq d(j,R)\) otherwise. Thus, the answer to this problem can be found as the sum of the following two values:

• the sum of \(d(j,R)\) over all vertices \(j\) contained in the subtree rooted at \(M\)
• the sum of \(d(j,L)\) over all vertices \(j\) not contained in the subtree rooted at \(M\)

We describe how to find the former. The latter can also be found in the same way with a small tweak.
Let \(j\) be an arbitrary vertex. Let \(v\) be the LCA of \(j\) and \(R\); then \(d(j,R) = dep_R + dep_j - 2dep_v\). Thus, fixing \(v\) and considering the sum of \(d(j,R)\) over vertices \(j\) such that the LCA of \(j\) and \(R\) is \(v\), it can be written as \(s(dep_R - 2dep_v) + \sum dep_j\), where \(s\) is the number of such vertices.
Consider the specific value of \(s\). If \(v = R\), then \(s = sz_v\); otherwise, \(s = sz_v - sz_u\), where \(u\) is the vertices you reach by traversing an edge from \(v\) toward \(R\).
Thus, considering the sum of \(s(dep_R - 2dep_v) + \sum dep_j\) over all \(v\), we have \(d(M,R) sz_M -2\sum_{v \in S_1} sz_v + \sum_{j \in S_2} dep_j\), where \(S_\) is the set of vertices that can be reachable from \(R\) toward \(R\) by traversing edges between \(0\) and \((d(M,R)-1)\) times, and \(S_2\) is the set of vertices that form the subtree rooted at \(M\).
The values so far can be found in an \(\mathrm{O}(1)\) if we know \(M\), by precalculating the sum of \(dep_u\) over vertices \(u\) in the subtree rooted at \(v\) and the sum of \(sz_u\) over the ancestors \(u\) of \(v\).
One can find \(M\) using LCA (Lowest Common Ancestor) or LA. Due to this computation, the time complexity is about \(\Theta(N + Q), \Theta(N \log N + Q)\), or \(\Theta((N+Q) \log N)\), all of which are fast enough with a proper implementation.