#include using namespace std; #define __ <<" "<< #define ___ <<" " #define bash push_back #define ALL(x) x.begin(),x.end() //#define int long long struct IoSetup { IoSetup() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } }IoSetup; using Int = int; using ll = long long; using pii = pair; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr int SMOD = 1000000007; constexpr int NMOD = 998244353; constexpr int dx[]={1,0,-1,0,1,1,-1,-1}; constexpr int dy[]={0,-1,0,1,-1,1,-1,1}; inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && xbool chmax(T &a, const T&b){if(abool chmin(T &a, const T&b){if(b struct Edge { int from, to; T cost; Edge(int to) : from(0), to(to), cost(T(1)) {} Edge(int to, T cost) : from(0), to(to), cost(cost) {} Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} const bool operator < (const Edge&e) const { return (this->cost == e.cost ? (this->from == e.from ? this->to < e.to : this->from < e.from) : this->cost < e.cost); } }; template using Graph = vector>>; template using Edges = vector>; template class HLD { private: void dfs_sz(int v) { for(auto &u:G[v]) if(u.to==par[v]) swap(u,G[v].back()); if(~par[v]) G[v].pop_back(); for(auto &u:G[v]){ par[u.to]=v; dep[u.to]=dep[v]+1; wei[u.to] = wei[v] + u.cost; dfs_sz(u.to); sub[v]+=sub[u.to]; if(sub[u.to]>sub[G[v][0].to]) swap(u,G[v][0]); } } void dfs_hld(int v,int c,int &pos) { vid[v]=pos++; inv[vid[v]]=v; type[v]=c; for(auto& u:G[v]){ if(u.to==par[v]) continue; head[u.to]=(u.to==G[v][0].to?head[v]:u.to); dfs_hld(u.to,c,pos); } } public: vector< vector> > G; vector vid, head, sub, par, dep, wei, inv, type; /* vid : HL分解後でのグラフでのid head: 頂点が属するheavy-pathのheadのid sub : 部分木のサイズ hvy : heavy-path上での次の頂点のid par : 親のid dep : 深さ wei : 根からのコストの総和 inv : HL分解前のid(添え字が分解後のid) type: 森をHL分解するときの属する木の番号 */ HLD(int n): G(n),vid(n,-1),head(n),sub(n,1), par(n,-1),dep(n,0),wei(n, 0), inv(n),type(n) {} // u <--> v void add_edge(int u,int v, Type cost = 1) { G[u].emplace_back(Edge(v, cost)); G[v].emplace_back(Edge(u, cost)); } // 構築 void build(vector rs={0}) { int c=0,pos=0; for(int r:rs){ dfs_sz(r); head[r]=r; dfs_hld(r,c++,pos); } } // 最小共通祖先 int lca(int u,int v) const { while(1){ if(vid[u]>vid[v]) swap(u,v); if(head[u]==head[v]) return u; v=par[head[v]]; } } // 頂点 v から k 個上った頂点 int climb(int v, int k) const { while(true) { const int h = head[v]; if(vid[v] - k >= vid[h]) return inv[vid[v] - k]; k -= vid[v] - vid[h] + 1; v = par[h]; } } // u, v 間の辺の個数 int distance(int u,int v) const { return dep[u]+dep[v]-2*dep[lca(u,v)]; } // u, v間の辺のコストの総和 Type pathWeight(int u, int v) const { return wei[u] + wei[v] - 2 * wei[lca(u, v)]; } // for_each(vertex) // [l, r) <- attention!! template void for_each(int u, int v, const F& f) { while(1){ if(vid[u]>vid[v]) swap(u,v); f(max(vid[head[v]],vid[u]),vid[v]+1); if(head[u]!=head[v]) v=par[head[v]]; else break; } } template T for_each(int u,int v,T ti,const Q &q,const F &f){ T l=ti,r=ti; while(1){ if(vid[u]>vid[v]){ swap(u,v); swap(l,r); } l=f(l,q(max(vid[head[v]],vid[u]),vid[v]+1)); if(head[u]!=head[v]) v=par[head[v]]; else break; } return f(l,r); } // for_each(edge) // [l, r) <- attention!! template void for_each_edge(int u, int v,const F& f) { while(1){ if(vid[u]>vid[v]) swap(u,v); if(head[u]!=head[v]){ f(vid[head[v]],vid[v]+1); v=par[head[v]]; }else{ if(u!=v) f(vid[u]+1,vid[v]+1); break; } } } }; template< typename Monoid, typename OperatorMonoid = Monoid > struct LazySegmentTree { using F = function< Monoid(Monoid, Monoid) >; using G = function< Monoid(Monoid, OperatorMonoid) >; using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >; int sz, height; vector< Monoid > data; vector< OperatorMonoid > lazy; const F f; const G g; const H h; const Monoid M1; const OperatorMonoid OM0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &M1, const OperatorMonoid OM0) : f(f), g(g), h(h), M1(M1), OM0(OM0) { sz = 1; height = 0; while(sz < n) sz <<= 1, height++; data.assign(2 * sz, M1); lazy.assign(2 * sz, OM0); } void set(int k, const Monoid &x) { data[k + sz] = x; } void build() { for(int k = sz - 1; k > 0; k--) { data[k] = f(data[2 * k + 0], data[2 * k + 1]); } } inline void propagate(int k) { if(lazy[k] != OM0) { lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]); lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]); data[k] = reflect(k); lazy[k] = OM0; } } inline Monoid reflect(int k) { return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]); } inline void recalc(int k) { while(k >>= 1) data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1)); } inline void thrust(int k) { for(int i = height; i > 0; i--) propagate(k >> i); } void update(int a, int b, const OperatorMonoid &x) { thrust(a += sz); thrust(b += sz - 1); for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) lazy[l] = h(lazy[l], x), ++l; if(r & 1) --r, lazy[r] = h(lazy[r], x); } recalc(a); recalc(b); } Monoid query(int a, int b) { thrust(a += sz); thrust(b += sz - 1); Monoid L = M1, R = M1; for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) L = f(L, reflect(l++)); if(r & 1) R = f(reflect(--r), R); } return f(L, R); } Monoid operator[](const int &k) { return query(k, k + 1); } template< typename C > int find_subtree(int a, const C &check, Monoid &M, bool type) { while(a < sz) { propagate(a); Monoid nxt = type ? f(reflect(2 * a + type), M) : f(M, reflect(2 * a + type)); if(check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template< typename C > int find_first(int a, const C &check) { Monoid L = M1; if(a <= 0) { if(check(f(L, reflect(1)))) return find_subtree(1, check, L, false); return -1; } thrust(a + sz); int b = sz; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) { Monoid nxt = f(L, reflect(a)); if(check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template< typename C > int find_last(int b, const C &check) { Monoid R = M1; if(b >= sz) { if(check(f(reflect(1), R))) return find_subtree(1, check, R, true); return -1; } thrust(b + sz - 1); int a = sz; for(b += sz; a < b; a >>= 1, b >>= 1) { if(b & 1) { Monoid nxt = f(reflect(--b), R); if(check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; signed main() { int n; cin >> n; using X = pair; using M = int64_t; LazySegmentTree seg(n, [](X a, X b){return X(a.first + b.first, a.second + b.second);}, [](X a, M b){return X(a.first + a.second * b, a.second);}, [](M a, M b){return a + b;}, X(), 0); for(int i = 0; i < n; i++) seg.set(i, X(1, 1)); seg.build(); HLD hl(n); for(int i = 1; i < n; i++) { int a, b; cin >> a >> b; hl.add_edge(a-1, b-1); } hl.build(); ll sum = 0; int q; cin >> q; while(q--) { int a, b; cin >> a >> b; a--, b--; int64_t ans = 0; hl.for_each(a, b, [&](int l, int r){ans += seg.query(l, r).first;}); hl.for_each(a, b, [&](int l, int r){seg.update(l, r, 1);}); sum += ans; } cout << sum << endl; return 0; }