#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i)) #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n' #define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair Pii; typedef vector vint; typedef vector vll; const ull INF = ULLONG_MAX; const ll MOD = 998244353; struct HLDecomposition{ public: int V; vector g; vint dep,par,head,size,inv; vint in,out; HLDecomposition(int size_) :V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V),t(0){} void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); } void build(int root=0){ par[root]=0; dfs_size(root); par[root]=-1; dfs_hld(root); } int lca(int u,int v){ while(1){ if(in[u]>in[v])swap(u,v); if(head[u]==head[v])return u; v=par[head[v]]; } } int distance(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } private: int t; void dfs_size(int v=0){ size[v]=1; for(int& u:g[v]){ if(par[u]>=0)continue; par[u]=v; dfs_size(u); size[v]+=size[u]; if(size[u]>size[g[v][0]]){ swap(u,g[v][0]); } } } void dfs_hld(int v=0){ in[v] = t++; inv[in[v]]=v; for(int& u:g[v]){ if(par[u]!=v)continue; head[u]=(u==g[v][0]?head[v]:u); dfs_hld(u); } out[v]=t; } }; template struct BIT_interval { vector dat1; vector dat2; BIT_interval(int n) : dat1(n+1),dat2(n+1) { } // add w [l,r) void add_interval(int l,int r, T w) { for (int k=l+1; k < dat1.size(); k += k&-k) dat1[k] -= w*l; for (int k=r+1; k < dat1.size(); k += k&-k) dat1[k] += w*r; for (int k=l+1; k < dat2.size(); k += k&-k) dat2[k] += w; for (int k=r+1; k < dat2.size(); k += k&-k) dat2[k] -= w; } T sum(int x) { T s = 0; for (int k=x; k > 0; k &= k-1) s += dat1[k]; for (int k=x; k > 0; k &= k-1) s += dat2[k]*x; return s; } }; int main(){ int N;cin>>N; HLDecomposition hld(N); repeat(i,N-1){ int u,v;cin>>u>>v;u--;v--; hld.add_edge(u,v); } hld.build(); BIT_interval bit(N); bit.add_interval(0,N,1); int Q;cin>>Q; ll ans = 0; repeat(q,Q){ int A,B;cin>>A>>B;A--;B--; int u=A,v=B; while(1){ if(hld.in[u]>hld.in[v])swap(u,v); ans += bit.sum(hld.in[v]+1)-bit.sum(max(hld.in[hld.head[v]],hld.in[u])); if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]]; else break; } u=A,v=B; while(1){ if(hld.in[u]>hld.in[v])swap(u,v); bit.add_interval(max(hld.in[hld.head[v]],hld.in[u]),hld.in[v]+1,1); if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]]; else break; } } cout << ans << endl; return 0; }