#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace sgt {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
int sum[200005*8], tag[200005*8];
void push_up(int i) {
sum[i] = sum[ls(i)] + sum[rs(i)];
}
void build(const int *a, int i, int l, int r) {
if (l == r) {
sum[i] = a[l];
return;
}
int mid = (l + r) / 2;
build(a, ls(i), l, mid);
build(a, rs(i), mid + 1, r);
push_up(i);
}
void settag(int i, int l, int r, int k) {
sum[i] += (r - l + 1) * k;
tag[i] += k;
}
void push_down(int i, int l, int r) {
if (!tag[i]) return;
int mid = (l + r) / 2;
settag(ls(i), l, mid, tag[i]);
settag(rs(i), mid + 1, r, tag[i]);
tag[i] = 0;
}
void update(int i, int l, int r, int ql, int qr, int k) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) return settag(i, l, r, k);
int mid = (l + r) / 2; push_down(i, l, r);
update(ls(i), l, mid, ql, qr, k);
update(rs(i), mid + 1, r, ql, qr, k);
push_up(i);
}
int query(int i, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return 0;
if (l >= ql && r <= qr) return sum[i];
int mid = (l + r) / 2; push_down(i, l, r);
return query(ls(i), l, mid, ql, qr) + query(rs(i), mid + 1, r, ql, qr);
}
}
int n, q, ans[200005];
vector<int> edges[200005];
vector<pair<int, int>> qrs[200005];
namespace tr {
int fa[21][200005], dep[200005], sz[200005], dfn[200005], dft, b[200005];
void init(int i) {
sz[i] = 1; dfn[i] = ++dft;
for (auto j : edges[i]) {
if (j == fa[0][i]) continue;
fa[0][j] = i;
dep[j] = dep[i] + 1;
init(j);
sz[i] += sz[j];
}
for (int j = 1; j <= 20; ++j) {
fa[j][i] = fa[j - 1][fa[j - 1][i]];
}
}
int jump(int x, int k) {
for (int l = 0; k; ++l, k >>= 1)
if (k & 1) x = fa[l][x];
return x;
}
int query_son(int i, int minus) {
return sgt::query(1, 1, n, dfn[i], dfn[i] + sz[i] - 1);
}
void update_t(int i, int k) {
sgt::update(1, 1, n, dfn[i], dfn[i] + sz[i] - 1, k);
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
x = jump(x, dep[x] - dep[y]);
int l = 20;
while (~l) {
if (fa[l][x] != fa[l][y]) {
x = fa[l][x];
y = fa[l][y];
}
--l;
}
return fa[0][x];
}
void dfs(int i) {
assert(sgt::query(1, 1, n, dfn[i], dfn[i]) == 0);
for (auto _ : qrs[i]) {
int id = _.first,p = _.second;
if (p < 0) p = -p, ans[id]+=sgt::sum[1]-query_son(p, 0);
else ans[id]+=query_son(p, 0);
}
for (auto j : edges[i]) {
if (j == fa[0][i]) continue;
update_t(j, -2);
update_t(1, +1);
dfs(j);
update_t(j, +2);
update_t(1, -1);
}
}
void preinit() {
init(1);
for (int i = 1; i <= n; ++i) b[dfn[i]] = dep[i];
sgt::build(b, 1, 1, n);
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
cin >> q;
tr::preinit();
for (int i = 1; i <= q; ++i) {
int x, y;
cin >> x >> y;
if (tr::dep[x] < tr::dep[y]) swap(x, y);
int lca = tr::lca(x, y);
int mid = tr::jump(x, (tr::dep[x] + tr::dep[y] - 2 * tr::dep[lca] - 1) / 2);
qrs[x].push_back({i, mid});
qrs[y].push_back({i, -mid});
}
tr::dfs(1);
for (int i = 1; i <= q; ++i) cout << ans[i] << "\n";
return 0;
}
https://atcoder.jp/contests/abc298/submissions/58578342