#include using namespace std; #include using namespace atcoder; using ll = long long; using P = pair; #define fix(x) fixed << setprecision(x) #define asc(x) x, vector, greater #define rep(i, n) for(ll i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() templatebool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} templatebool chmax(T&a, const T&b){if(aを引数に与えると生成されるデータ構造であること // F: S->Sの関数 // R(V v, int l, int r, F x): 区間[l,r)操作クエリ // Q(V v, int l, int r): 区間[l,r)演算処理クエリ 返り値の型はSであること template struct HLD{ int n, root; vector> g; vector data_; V data; vector st_size, label, par, top; HLD(){} HLD(const vector>& _g, int r = 0) : n(_g.size()), g(_g), root(r), data_(n), st_size(n,1), label(n), par(n,-1), top(n){ par[root] = -1; dfs_size(root); int num = 0; dfs_hld(root, num, root); data = V(data_); } void dfs_size(int now){ for(Edge& edge:g[now]){ if(par[now]==edge.to) continue; par[edge.to] = now; dfs_size(edge.to); st_size[now] += st_size[edge.to]; if(st_size[g[now][0].to] < st_size[edge.to]) swap(g[now][0], edge); } } void dfs_hld(int now, int& num, int t){ label[now] = num, top[now] = t; for(Edge& edge:g[now]){ if(edge.to==par[now]) continue; data_[num++] = edge.w; dfs_hld(edge.to, num, (edge==g[now][0] ? t : edge.to)); } } // {op(u,...,v), lca(u,v)} pair prod(int u, int v){ S res = e(); while(top[u]!=top[v]){ if(label[u]>label[v]){ res = op(res, Q(data, label[top[u]] - (top[u]!=root), label[u])); u = (top[u]!=root ? par[top[u]] : top[u]); }else{ res = op(res, Q(data, label[top[v]] - (top[v]!=root), label[v])); v = (top[v]!=root ? par[top[v]] : top[v]); } } res = op(res, (label[u]; struct Edge{ int to; S w; bool operator==(Edge& edge){ return to==edge.to; } }; void R(SEG& seg, int l, int r, ll x){ seg.apply(l,r,x); } S Q(SEG& seg, int l, int r){ return seg.prod(l,r); } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector> g(n); rep(i,n-1){ int u,v; cin >> u >> v; u--; v--; g[u].push_back({v,S(0,1)}); g[v].push_back({u,S(0,1)}); } HLD hld(g); int q; cin >> q; ll ans = 0, t = 0; while(q--){ int u,v; cin >> u >> v; u--; v--; int r = hld.apply(u,v,1); if(r) hld.apply(r,hld.par[r],1); else t++; ans += hld.prod(u,v).first.val; if(r) ans += hld.prod(r,hld.par[r]).first.val; else ans += t; } cout << ans << '\n'; return 0; }