適当に根を取り木を根付き木とします。また、頂点 \(v\) の深さ（すなわち、根からの距離）を \(dep_v\) 、頂点 \(v\) を根とする部分木の頂点数を \(sz_v\) とおきます。
適切な前計算のもとで、各クエリに十分高速に答えることを考えましょう。整数 \(L,R\) がクエリで与えられたとしてこれに対する答えを求めていきます。
必要であれば適切に swap することで \(dep_L < dep_R\) とします。足し合わせる対象は \(\min(d(j,L), d(j,R))\) ですが、\(d(j,L)\) と \(d(j,R)\) の大小関係について考えます。
\(R\) から根方向に \(\lfloor \frac{(d(L,R)-1)}{2} \rfloor\) 進んだ頂点を \(M\) とおくと、\(dep_L < dep_R\) より \(M\) は \(L\) と \(R\) の LCA の子孫なので、頂点 \(j\) は \(M\) を根とする部分木の頂点である場合 \(d(j,L) > d(j,R)\) を満たし、そうでない場合 \(d(j,L) \leq d(j,R)\) となります。よって以下の 2 つの値を求め、足し合わせると本問題の答えを得ることができます。

• \(M\) を根とする部分木に含まれる頂点 \(j\) に対する \(d(j,R)\) の総和
• \(M\) を根とする部分木に含まれない頂点 \(j\) に対する \(d(j,L)\) の総和

前者の求め方について具体的に説明します。後者については、少しだけ手間は増えますがほぼ同様に求めることができます。
\(j\) を適当な頂点とします。\(v\) を \(j\) と \(R\) の LCA とすると、\(d(j,R) = dep_R + dep_j - 2dep_v\) です。よって \(v\) を固定し、\(j\) と \(R\) の LCA が \(v\) となる頂点 \(j\) に対する \(d(j,R)\) の和を考えると、そのような頂点の数を \(s\) として \(s(dep_R - 2dep_v) + \sum dep_j\) と表せます。
\(s\) の値について具体的に考えると、\(v = R\) のとき \(s = sz_v\) 、そうでないとき \(v\) から \(R\) 方向に距離 \(1\) だけ進んだ頂点を \(u\) として \(s = sz_v - sz_u\) です。
よって各 \(v\) に対する \(s(dep_R - 2dep_v) + \sum dep_j\) の和を整理すると、\(d(M,R) sz_M -2\sum_{v \in S_1} sz_v + \sum_{j \in S_2} dep_j\) となります。ただし、 \(S_1\) は \(R\) から \(M\) 方向に \(0\) 以上 \(d(M,R)\) 未満進んで到達する頂点の集合で、\(S_2\) は \(M\) を根とする部分木の頂点の集合です。
上の値は、各頂点 \(v\) に対し \(v\) を根とする部分木の頂点 \(u\) に対する \(dep_u\) の和と \(v\) の祖先 \(u\) に対する \(sz_u\) の和を前計算しておけば \(M\) がわかっているとき \(\mathrm{O}(1)\) で求められます。
\(M\) を求めるには LCA や LA を求めるアルゴリズムなどを使えばよく、LCA や LA の計算量により時間計算量は全体で \(\Theta(N + Q), \Theta(N \log N + Q), \Theta((N+Q) \log N)\) などになり、適切な実装のもと十分高速に答えを得ることができます。