简单题。
因为有 \(\min\) 不好做，容易想到讨论 \(d(i, L)\) 和 \(d(i, R)\) 的大小。
令 \(p = \text{LCA}(L, R)\)，\(dep_L > dep_R, dist = dep_L + dep_R - 2\times dep_p\)，\(now\) 满足 \(dep_L - dep_{now} = \lfloor\dfrac{dist}{2}\rfloor\)
则 \(L\) 一定在 \(now\) 的子树内，且对于 \(\forall i\in \{\text{subtree}(now)\}\) 时均有 \(d(i, L) \le d(i, R)\)，否则 \(d(i, L) > d(i, R)\)。其中 \(\text{subtree}(x)\) 表示 \(x\) 的子树。
容易想到求一个点到其他点的距离和。
令 \(val_i\) 表示 \(\sum\limits_{j = 1}^{n} d(i, j)\)。
在 dfs 时处理一下即可，显然可以做到 \(\mathcal{O}(n)\)。
最后再将 \(dist\) 奇偶讨论一下即可。
时间复杂度：\(\mathcal{O}(n + m\log n)\)，可以使用线性 LCA 做到 \(\mathcal{O}(n + m)\)
代码：
const int N = 2e5 + 10;
int n, m;
int siz[N], d[N], fa[N][20];
ll dis[N], v[N];
vector<int> e[N];
void dfs1(int u, int f) {
d[u] = d[f] + 1, siz[u] = 1, fa[u][0] = f;
for (int i = 1; i <= 18; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int v : e[u])
if (v != f) {
dfs1(v, u);
siz[u] += siz[v];
dis[u] += dis[v] + siz[v];
}
}
void dfs2(int u, int f) {
if (u == 1)
v[u] = dis[u];
else
v[u] = v[f] + (siz[1] - siz[u]) - siz[u];
for (int v : e[u])
if (v != f)
dfs2(v, u);
}
int lca(int u, int v) {
if (d[u] < d[v])
swap(u, v);
for (int i = 18; i >= 0; i--)
if (d[fa[u][i]] >= d[v])
u = fa[u][i];
if (u == v)
return u;
for (int i = 18; i >= 0; i--)
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
int tonode(int u, int st) {
for (int i = 18; i >= 0; i--)
if (st >> i & 1)
u = fa[u][i];
return u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].pb(v), e[v].pb(u);
}
dfs1(1, 0), dfs2(1, 0);
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
if (d[l] < d[r])
swap(l, r);
int p = lca(l, r), dist = d[l] + d[r] - 2 * d[p];
if (dist % 2 == 0) {
int now = tonode(l, dist / 2);
cout << v[l] + v[r] - v[now] - 1ll * n * dist / 2 << "\n";
} else {
int now = tonode(l, dist / 2);
cout << v[l] + v[r] - v[now] - 1ll * n * (dist / 2) - siz[now] << "\n";
}
}
return 0;
}