頂点 \(v\) に対し，\(f(v)=\displaystyle \sum_{i=1}^N d(i,v)\) とします．

[1] \(d(L,R)\) が偶数のとき

\(D=d(L,R)\) とし，頂点 \(L,R\) の中点 (頂点 \(L\) から頂点 \(R\) に向かって \(D/2\) だけ進んだところにある頂点) を \(M\) とします．このとき，\(\min(d(v,L),d(v,R))=d(v,L)+d(v,R)-d(v,M)-\dfrac{D}{2}\) が成り立ちます．

（理由：ある頂点 \(v\) について \(d(v,L)\leq d(v,R)\) が成り立っているとき，頂点 \(v\) から \(R\) のパスは必ず頂点 \(M\) を通っています．よって，\(d(v,R)=d(v,M)+d(M,R)=d(v,M)+\dfrac{D}{2}\) が成り立ちます．\(d(v,L)\geq d(v,R)\) の場合も同様です．）

よって，求めるものについて， \(\displaystyle \sum_{i=1}^N d(i,L)+d(i,R)-d(i,M)-\dfrac{D}{2}=f(L)+f(R)-f(M)-\dfrac{ND}{2}\) が成り立ちます．

[2] \(d(L,R)\) が奇数のとき

\(D=d(L,R)\) とし，頂点 \(L\) から頂点 \(R\) に向かって \((D-1)/2,(D+1)/2\) だけ進んだところにある頂点を \(M_1,M_2\) とします．[1] と似たような理由により，求めるものは \(f(L)+f(R)-f(M_1)-\dfrac{N(D-1)}{2}-(辺 \{M_1,M_2\} で木を分断したときの，M_1 側の頂点数)\) になります．

(追記) 求めるものは，より簡潔に \(f(L)+f(R)-\dfrac{f(M_1)}{2}-\dfrac{f(M_2)}{2}-\dfrac{ND}{2}\) と表わすことができます（解説放送より）．

以上で登場した，

• 各頂点に対する \(f(v)\) の値
• 頂点 \(u\) から \(v\) に向かって \(d\) だけ進んだところにある頂点
• 辺 \(\{u,v\}\) で木を分断したときの，\(u\) 側の頂点数

を前計算などにより高速に求められるようにしておけば，各質問に対して \(O(\log N)\) などで答えを求めることができます．

(補足) それぞれの求め方についてです．

• 各頂点に対する \(f(v)\) の値：ABC220F でそのまま出題されています．
• 頂点 \(u\) から \(v\) に向かって \(d\) だけ進んだところにある頂点：例えば，ダブリングを用いて LCA を求める方法を応用するとできます．Jump on Tree (LC) でそのまま出題されています．
• 辺 \(\{u,v\}\) で木を分断したときの，\(u\) 側の頂点数：適当に根付き木にすると，各頂点の部分木のサイズが分かればよいので，DFS で求められます．