#include #include #include #include using namespace std; /* include file*/ #include #include using namespace std; template struct LazySegment { using Func = function; vector node; vector lazy; vector lazyFlag; int n; Monoid ide; Monoid lazy_init; Monoid func(Monoid a,Monoid b){ return a + b; } Monoid lazy_make(int l,int r,Monoid x,Monoid lazy){ return lazy + (r - l) * x; } Monoid lazy_effect(Monoid node,Monoid lazy){ return node + lazy; } Monoid lazy_throw(Monoid from,Monoid to){ return to + from / 2; } LazySegment(const vector init, Monoid ide_, Monoid lazy_i) : ide(ide_), lazy_init(lazy_i) { n = 1; int sz = init.size(); while (n < sz) n *= 2; node.resize(n * 2 - 1, ide); lazy.resize(n * 2 - 1, lazy_init); lazyFlag.resize(n * 2 - 1, false); for (int i = 0; i < sz; i++) node[i + n - 1] = init[i]; for (int i = n - 2; i >= 0; i--) node[i] = func(node[i * 2 + 1], node[i * 2 + 2]); } void eval(int k, int l, int r) { if (lazyFlag[k]) { node[k] = lazy_effect(node[k], lazy[k]); if (r - l > 1) { lazy[2 * k + 1] = lazy_throw(lazy[k], lazy[2 * k + 1]); lazy[2 * k + 2] = lazy_throw(lazy[k], lazy[2 * k + 2]); lazyFlag[2 * k + 1] = true; lazyFlag[2 * k + 2] = true; } lazyFlag[k] = false; lazy[k] = lazy_init; } } void update_inter(int a, int b, Monoid x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[k] = lazy_make(l, r, x, lazy[k]); lazyFlag[k] = true; eval(k, l, r); } else { update_inter(a, b, x, k * 2 + 1, l, (l + r) / 2); update_inter(a, b, x, k * 2 + 2, (l + r) / 2, r); node[k] = func(node[k * 2 + 1], node[k * 2 + 2]); } } Monoid get_inter(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (r <= a || b <= l) return ide; if (a <= l && r <= b) return node[k]; Monoid lm = get_inter(a, b, k * 2 + 1, l, (l + r) / 2); Monoid rm = get_inter(a, b, k * 2 + 2, (l + r) / 2, r); return func(lm, rm); } }; #include using i64 = long long; struct HLDecomposition{ int n,pos; vector > G; vector vid,head,hvy,par,dep,inv,sub; LazySegment seg; HLDecomposition(int sz): n(sz),pos(0),G(n), vid(n,-1),head(n),hvy(n,-1), par(n),dep(n),inv(n),sub(n,1),seg(vector(n,0),0,0){} void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } void dfs(int rt){ typedef pair T; stack st; par[rt] = -1; dep[rt] = 0; st.push(make_pair(rt,0)); while(!st.empty()){ int v= st.top().first; int &i = st.top().second; if(i < (int)G[v].size()){ int u = G[v][i++]; if(u == par[v]) continue; par[u] = v; dep[u] = dep[v] + 1; st.push(make_pair(u,0)); } else{ st.pop(); int res = 0; for(int i = 0;i < (int)G[v].size();i++){ int u = G[v][i]; if(u == par[v]) continue; sub[v] += sub[u]; if(res < sub[u]) res = sub[u],hvy[v] = u; } } } } void bfs(int r){ int &k = pos; queue q; q.push(r); while(!q.empty()){ int h = q.front(); q.pop(); for(int i = h;i != -1;i = hvy[i]){ vid[i] = k++; inv[vid[i]] = i; head[i] = h; for(int j = 0;j < (int)G[i].size();j++){ int u = G[i][j]; if(u != par[i] && u != hvy[i]) q.push(u); } } } } void build(int r){ dfs(r); bfs(r); } void f(int l,int r){ seg.update_inter(l,r + 1,1); } void for_vertex(int u,int v){ while(1){ if(vid[u] > vid[v]) swap(u,v); f(max(vid[head[v]],vid[u]),vid[v]); if(head[u] != head[v]) v= par[head[v]]; else break; } } void for_edge(int u,int v){ while(1){ if(vid[u],vid[v]) swap(u,v); if(head[u] != head[v]){ f(vid[head[v]],vid[v]); v = par[head[v]]; } else{ if(u != v) f(vid[u] + 1,vid[v]); break; } } } int lca(int u,int v){ while(1){ if(vid[u] > vid[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)]; } }; #include using namespace std; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) #define all(x) x.begin(),x.end() int main(){ int N; cin >> N; HLDecomposition hld(N); rep(i,0,N - 2){ int a,b; cin >> a >> b; a--; b--; hld.add_edge(a,b); } hld.build(0); int Q; cin >> Q; rep(i,0,Q - 1){ int a,b; cin >> a >> b; a--; b--; hld.for_vertex(a,b); } i64 ans = 0; rep(i,0,N - 1){ i64 a = hld.seg.get_inter(i,i + 1); ans += a * (a + 1) / 2; } cout << ans << endl; }