#include #define rep(i,n)for(int i=0;i<(n);i++) using namespace std; typedef long long ll; #ifndef MAX #define MAX 400000 #endif //Range Add Query+Range Sum Query template class RAQ_RSQ { public: int n; T dat[MAX], lazy[MAX], ZERO; void init(int n_) { ZERO = T(); n = 1; while (n < n_)n <<= 1; for (int i = 0; i < 2 * n - 1; i++) { dat[i] = lazy[i] = ZERO; } } inline void push(int k, int s) { dat[k] = dat[k] + lazy[k] * s; if (k < n - 1) { lazy[k * 2 + 1] = lazy[k * 2 + 1] + lazy[k]; lazy[k * 2 + 2] = lazy[k * 2 + 2] + lazy[k]; } lazy[k] = ZERO; } inline void update_node(int k) { dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2]; } inline void update(int a, int b, T x, int k, int l, int r) { push(k, r - l); if (r <= a || b <= l)return; if (a <= l&&r <= b) { lazy[k] = lazy[k] + x; push(k, r - l); return; } update(a, b, x, k * 2 + 1, l, (l + r) / 2); update(a, b, x, k * 2 + 2, (l + r) / 2, r); update_node(k); } inline T query(int a, int b, int k, int l, int r) { push(k, r - l); if (r <= a || b <= l)return ZERO; if (a <= l&&r <= b)return dat[k]; T lb = query(a, b, k * 2 + 1, l, (l + r) / 2); T rb = query(a, b, k * 2 + 2, (l + r) / 2, r); update_node(k); return lb + rb; } inline void update(int a, int b, T x) { update(a, b, x, 0, 0, n); } inline void update(int a, T x) { update(a, a + 1, x); } inline T query(int a, int b) { return query(a, b, 0, 0, n); } inline T query(int a) { return query(a, a + 1); } }; RAQ_RSQseg; vectorE[200000]; int par[200000],d[200000],sub[200000]; int chain[200000],vid[200000]; int node_num; void dfs(int v,int p,int dep){ par[v]=p;d[v]=dep; sub[v]=1; for(int u:E[v]){ if(u==p)continue; dfs(u,v,dep+1); sub[v]+=sub[u]; } } void hld(int v,int k){ chain[v]=k; vid[v]=node_num++; int Max=0,id=-1; for(int u:E[v]){ if(u==par[v])continue; if(Maxd[chain[v]])swap(u,v); if(chain[u]==chain[v]){ seg.update(min(vid[u],vid[v]),max(vid[u],vid[v])+1,1); break; } else{ seg.update(vid[chain[v]],vid[v]+1,1); v=par[chain[v]]; } } } int main(){ int n;scanf("%d",&n); rep(i,n-1){ int u,v;scanf("%d%d",&u,&v);u--;v--; E[u].push_back(v);E[v].push_back(u); } dfs(0,-1,0); hld(0,0); seg.init(n); int q;scanf("%d",&q); rep(i,q){ int a,b;scanf("%d%d",&a,&b);a--;b--; update(a,b); } ll ans=0; rep(i,n){ ll a=seg.query(vid[i]); ans+=(a+1)*a/2; } cout<