#include #include using namespace std; using namespace atcoder; class HeavyLightDecomposition{ private: int n; vector> g; vector siz, par, dep, top, in, out; void dfs_siz(int v, int p){ par[v] = p; for(int &nv:g[v]){ if(nv==p){ if(nv==g[v].back()) break; swap(nv, g[v].back()); } dfs_siz(nv, v); siz[v] += siz[nv]; if(siz[nv]>siz[g[v][0]]){ swap(nv, g[v][0]); } } } void dfs_hld(int v, int p, int &i){ in[v] = i++; for(int &nv:g[v]){ if(nv==p) continue; dep[nv] = dep[v]+1; if(nv==g[v][0]) top[nv] = top[v]; else top[nv] = nv; dfs_hld(nv, v, i); } out[v] = i; } public: HeavyLightDecomposition(const int _n=0): n(_n), g(_n), siz(_n, 1), par(_n, -1), dep(_n), top(_n), in(_n), out(_n){} void add_edge(int u, int v){ g[u].push_back(v); g[v].push_back(u); } void build(){ dfs_siz(0, -1); int i{}; dfs_hld(0, -1, i); } int depth(int v) const { return dep[v]; } int lca(int u, int v) const { while(true){ if(in[u]>in[v]) swap(u, v); if(top[u]==top[v]) return u; v = par[top[v]]; } } void subtree_query(int u, const function &func) const{ func(in[u], out[u]); } void path_node_query(int u, int v, const function &func) const { while(true){ if(in[u]>in[v]) swap(u, v); func(max(in[u], in[top[v]]), in[v]+1); if(top[u]==top[v]) break; v = par[top[v]]; } } void path_edge_query(int u, int v, const function &func) const { while(true){ if(in[u]>in[v]) swap(u, v); if(top[u]==top[v]){ if(u==v) break; func(in[u]+1, in[v]+1); }else{ func(in[top[v]], in[v]+1); v = par[top[v]]; } } } }; struct S{ long long value; int size; }; using F = long long; S op(S a, S b){ return {a.value+b.value, a.size+b.size}; } S e(){ return {0, 0}; } S mapping(F f, S x){ return {x.value + f*x.size, x.size}; } F composition(F f, F g){ return f+g; } F id(){ return 0; } int main(){ int N; cin >> N; HeavyLightDecomposition hld(N); for(int i=0; i> u >> v; u--, v--; hld.add_edge(u, v); } hld.build(); vector v(N, {0, 1}); lazy_segtree seg(v); long long ans = 0; int Q; cin >> Q; for(;Q--;){ int u, v; cin >> u >> v; u--, v--; hld.path_node_query(u, v, [&](int a, int b) -> void{ seg.apply(a, b, 1); }); hld.path_node_query(u, v, [&](int a, int b) -> void{ ans += seg.prod(a, b).value; }); } cout << ans << endl; }