都 3202 年了，我还是永远喜欢正向计数（bushi）。
显然是 CF1336F 弱化版。值得一提的是，在 standing 上有一个老哥，交了一份很神奇的代码，好像拼了 CF1336F 的 std，然后拼了两份，一减就求得答案。
考虑分类计数，目前我们有两条链 \(x \to y\) 和 \(p\to q\)。
记录 \(l_{x, y}\) 为两条链底部分别为 \(x, y\) 的 LCA。
\(l_{x, y} = l_{p, q}\)
这个 case 建议正难则反，考虑为所有过这个点的 chains 的个数 \(\dfrac{size \times (size - 1)}{2}\) 减去有一个子树走向相同，再加上有两个子树走向相同。
这个是简单的。
\(l_{x, y} \not = l_{p, q}\)
容易发现深度大的那个点必然再另一个路径上。考虑钦定前者为 \(x \to y\) 用这个来计数。考虑树上差分，那么可以从 \(l_{x, y}\) 的子树内的一个点走上来且与 \(x \to l_{x, y}, l_{x, y} \to y\) 这两颗子树不交的点才是和法的。结合树状数组可以做到 \(1\log\) 。
注意 \(l_{x, y} = x\) 之类的，这些情况都要在计算贡献时加特判，具体细节可以参考代码。
我写了一份比较清真的实现如下：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
using namespace std;
typedef long long ll;
const int _ = 4e5 + 5, mod = 998244353;
namespace FenwickIndex {
#define lowbit(x) (x & -x)
int sz;
int c[_];
void init (int tot) { memset(c, 0, sizeof(c)); sz = tot; }
void add (int x, int k) { while (x <= sz) c[x] += k, x += lowbit(x); }
ll query (int x) {
ll res = 0;
while (x) res += c[x], x -= lowbit(x);
return res;
}
ll querysum (int l, int r) {
return query(r) - query(l - 1);
}
} using namespace FenwickIndex;
int n, m, dfc;
ll ret;
int dfn[_], ed[_], dep[_], anc[_][20];
vector <int> e[_];
vector <pair<int, int> > ad[_];
void dfs1 (int x, int fa) {
dep[x] = dep[fa] + 1, anc[x][0] = fa;
dfn[x] = ++ dfc;
rep(i, 1, 19) anc[x][i] = anc[anc[x][i - 1]][i - 1];
for (int y : e[x]) if (y ^ fa) dfs1(y, x);
ed[x] = dfc;
}
int LCA (int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int d = (dep[x] - dep[y]);
rep(i, 0, 19) if (d & (1 << i)) x = anc[x][i];
if (x == y) return x;
per(i, 19, 0) if (anc[x][i] != anc[y][i]) x = anc[x][i], y = anc[y][i];
return anc[x][0];
}
int kthanc (int x, int k) {
if (k == -1) return x;
rep(i, 0, 19) if (k & (1 << i)) x = anc[x][i]; return x;
}
int tmp[_];
map <pair<int, int>, int> mp;
vector <pair<int, int> > chain[_];
void dfs2 (int x, int fa) {
int num = chain[x].size();
ll res = 1ll * (num - 1) * num / 2, de = 0;
for (auto & [u, v] : chain[x]) tmp[u] ++, tmp[v] ++, mp[{u, v}] ++;
for (auto & [u, v] : chain[x]) {
if (u != x) de += tmp[u] - 1;
if (v != x) de += tmp[v] - 1;
if (u != x && v != x) de -= mp[{u, v}] - 1;
}
res -= de / 2ll, ret += res;
for (auto & [u, v] : chain[x]) tmp[u] = tmp[v] = mp[{u, v}] = 0;
for (auto & [u, v] : chain[x]) {
ll nd = querysum(dfn[x], ed[x]);
if (u != x) nd -= querysum(dfn[u], ed[u]);
if (v != x) nd -= querysum(dfn[v], ed[v]);
ret += nd;
}
for (auto & [p, k] : ad[x]) add(dfn[p], k);
for (int y : e[x]) if (y ^ fa) dfs2(y, x);
}
int main() {
/*
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
黛拉可玛莉·岗德森布莱德，一亿年一遇美少女。
*/
cin >> n;
init(n + 2);
rep(i, 1, n - 1) {
int x, y;
scanf("%d%d", & x, & y);
e[x].push_back(y), e[y].push_back(x);
}
dfs1(1, 0);
cin >> m;
rep(i, 1, m) {
int x = 1, y = 1, lc;
scanf("%d%d", & x, & y);
lc = LCA(x, y);
int a = kthanc(x, dep[x] - dep[lc] - 1), b = kthanc(y, dep[y] - dep[lc] - 1);
if (a < b) swap(a, b);
chain[lc].push_back({a, b});
if (x != lc) ad[lc].push_back({x, 1}), ad[x].push_back({x, -1});
if (y != lc) ad[lc].push_back({y, 1}), ad[y].push_back({y, -1});
}
dfs2(1, 0);
cout << ret << endl;
return 0;
}