#include #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair Pll; typedef vector vll; const ll INF = LLONG_MAX/10; const ll MOD = 1e9+7; template struct BIT_interval { vector dat1; vector dat2; BIT_interval(int n) : dat1(n+1,0),dat2(n+1,0) { } // add w [l,r) void add_interval(int l,int r, T w) { for (int k=l+1; k < (int)dat1.size(); k += k&-k) dat1[k] -= w*l; for (int k=r+1; k < (int)dat1.size(); k += k&-k) dat1[k] += w*r; for (int k=l+1; k < (int)dat2.size(); k += k&-k) dat2[k] += w; for (int k=r+1; k < (int)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; } T operator[](const int k){return sum(k+1)-sum(k);} }; struct HLDecomposition{ private: int t; void dfs_size(int v=0){ size[v]=1; for(int& u:g[v]){ if(par[u]>=0){ swap(u,g[v].back()); if(u==g[v].back())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; } public: int V; vector> g; vector dep,par,head,size,inv; vector in,out; HLDecomposition(int size_) :t(0),V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V){} 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)]; } int operator[](const int &k){ return in[k]; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N;cin>>N; HLDecomposition hld(N); for(ll i=0;i>u>>v;u--;v--; hld.add_edge(u,v); } hld.build(); BIT_interval bit(N); bit.add_interval(0,N,1); ll Q;cin>>Q; ll ans =0; for(ll q=0;q>A>>B;A--;B--; ll u=A,v=B; while(1){ if(hld[u]>hld[v])swap(u,v); ans += bit.sum(hld[v]+1)-bit.sum(max(hld[hld.head[v]],hld[u])); if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]]; else break; } u=A,v=B; while(1){ if(hld[u]>hld[v])swap(u,v); bit.add_interval(max(hld[hld.head[v]],hld[u]),hld[v]+1,1); if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]]; else break; } } cout<