#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "limits.h" #define rep(i, a, b) for (long long (i) = (a); i < (b); i++) #define all(i) i.begin(), i.end() #define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) void debug_out(){std::cerr< void debug_out(H head,T... tail){ std::cerr<<" "< std::ostream& operator<<(std::ostream& os, std::pair pa) { return os << pa.first << " " << pa.second; } template std::ostream& operator<<(std::ostream& os, std::vector vec) { for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os; } template inline bool chmax(T1& a,T2 b){return a inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);} long long pow_mod(long long a, long long b, long long mod=-1) { if ((a == 0)||(mod!=-1&&a%mod==0))return 0; long long x = 1; while (b > 0) { if (b & 1)x = (mod!=-1)?(x * a) % mod:x*a; a = (mod!=-1)?(a * a) % mod:a*a; b >>= 1; } return x; } // const long long MOD = 998244353; const long long MOD = 1e9 + 7; using ll = long long; using P = std::pair; //LowestCommonAncestor //ダブリングを使う 前処理O(Nlog N),クエリO(log N) class LowestCommonAncestor{ using ll=long long; private: ll n,bit; std::vector depth; std::vector> par_doubling,graph; ll getbit(ll temp){ ll a=1; while(temp>0){ a++; temp>>=1; } return a; } void dfs(ll now,ll par,ll dep){ depth[now]=dep; if(par!=-1)par_doubling[now][0]=par; else par_doubling[now][0]=now; for(auto e:graph[now]){ if(e!=par){ dfs(e,now,dep+1); } } } void doubling(){ for(ll i=1;i>& g,ll root_):graph(g),n(g.size()),bit(getbit(g.size())), depth(n),par_doubling(n,std::vector(bit)){ dfs(root_,-1,0); doubling(); } ll query(ll a,ll b){ if(depth[a]>i)&1)a=par_doubling[a][i]; } if(a==b)return a; for(ll i=bit-1;i>=0;i--){ if(par_doubling[a][i]!=par_doubling[b][i]){ a=par_doubling[a][i]; b=par_doubling[b][i]; } } return par_doubling[a][0]; } }; //遅延セグ木 template class LazySegmentTree{ private: int n,n0; std::vector dat; std::vector lazy; T init_t; E init_e; using F=std::function; using G=std::function; using H=std::function; using P=std::function; F f; G g; H h; P p; T update(int a,int b,E val,int l,int r,int k){ if(lazy[k]!=init_e){ if(k dat_=std::vector(),P p_=[](E a,int n){return a;}) :n(n_),init_t(t),init_e(e),f(f_),g(g_),h(h_),p(p_){ n0=1; while(n0(2*n0-1,init_t); lazy=std::vector(2*n0-1,init_e); if(n_==dat_.size()){ for(int i=0;i=0;i--)dat[i]=f(dat[2*i+1],dat[2*i+2]); } } void update(int a,int b,E val){ update(a,b,val,0,n0,0); } T query(int a,int b){ return query(a,b,0,n0,0); } }; int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); ll n; std::cin>>n; std::vector> graph(n); std::vector par(n),sz(n),in(n),nxt(n); rep(i,0,n-1){ ll u,v; std::cin>>u>>v; u--;v--; graph[u].push_back(v); graph[v].push_back(u); } auto dfs_sz=[&](auto f,ll now,ll pa)->void{ sz[now]=1; par[now]=pa; for(auto itr=graph[now].begin();itr!=graph[now].end();){ if(*itr==pa){ itr=graph[now].erase(itr); }else{ f(f,*itr,now); sz[now]+=sz[*itr]; if(sz[*itr]>sz[*graph[now].begin()]){ std::iter_swap(itr,graph[now].begin()); } itr++; } } }; dfs_sz(dfs_sz,0,-1); LowestCommonAncestor lca(graph,0); ll cnt=0; auto dfs_hld=[&](auto f,ll now)->void{ in[now]=cnt++; for(auto u:graph[now]){ nxt[u]=(u==graph[now][0]?nxt[now]:u); f(f,u); } }; dfs_hld(dfs_hld,0); auto sum=[](ll a,ll b){return a+b;}; LazySegmentTree seg(n,sum,sum,sum,0,0,std::vector(n,1),[](ll a,int n){return a*n;}); ll ans=0; ll q; std::cin>>q; rep(_,0,q){ ll v[2]; std::cin>>v[0]>>v[1]; v[0]--;v[1]--; ll l=lca.query(v[0],v[1]); rep(i,0,2){ while(1){ if(nxt[v[i]]==nxt[l]){ ans+=seg.query(in[l]+i,in[v[i]]+1); seg.update(in[l]+i,in[v[i]]+1,1); break; } ans+=seg.query(in[nxt[v[i]]],in[v[i]]+1); seg.update(in[nxt[v[i]]],in[v[i]]+1,1); v[i]=par[nxt[v[i]]]; } } } std::cout<