#include using namespace std; #include using namespace atcoder; #define int long long typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; typedef pair pi; typedef vector vi; typedef vector vd; typedef vector vb; typedef vector vs; typedef vector vc; typedef vector> vp; typedef vector> vvi; typedef vector> vvd; typedef vector> vvb; typedef vector> vvs; typedef vector> vvc; typedef vector>> vvp; typedef vector>> vvvi; typedef vector>>> vvvvi; typedef queue qi; typedef queue> qp; template using vvv = vector>>; template using vvvv = vector>>>; template using pq = priority_queue; template using pqg = priority_queue, greater>; #define _PI 3.14159265358979323846 #define _E 2.7182818284590452354 #define fi first #define se second #define mset multiset #define uset unordered_set #define umap unordered_map #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define td typedef #define elif else if #define unless(a) if (!(a)) #define el endl #define all(obj) (obj).begin(), (obj).end() #define rall(obj) (obj).rbegin(), (obj).rend() #define acc(a) accumulate(all(a), 0LL) #define lb(v, a) (lower_bound(begin(v), end(v), a) - begin(v)) #define ub(v, a) (upper_bound(begin(v), end(v), a) - begin(v)) #define cbit(x) __builtin_popcountll(x) #define bits(x) (1LL << (x)) #define gbit(a, i) ((a >> i) & 1) #define topbit(t) (t == 0 ? -1 : 63 - __builtin_clzll(t)) #define botbit(t) (t == 0 ? 64 : __builtin_ctzll(t)) #define rep1(a) for (int i = 0; i < (int)a; i++) #define rep2(i, a) for (int i = 0; i < (int)a; i++) #define rep3(i, a, b) for (int i = a; i < (int)b; i++) #define rep4(i, a, b, c) for (int i = a; i < (int)b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(n) for (ll i = n; i--;) #define rrep2(i, n) for (ll i = n; i--;) #define rrep3(i, a, b) for (ll i = b; i-- > (a);) #define rrep4(i, a, b, c) \ for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c) #define rrep(...) \ overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define fore1(i, a) for (auto &&i : a) #define fore2(x, y, a) for (auto &&[x, y] : a) #define fore3(x, y, z, a) for (auto &&[x, y, z] : a) #define fore(...) overload4(__VA_ARGS__, fore3, fore2, fore1)(__VA_ARGS__) // debug methods // usage: debug(x,y); #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x #define debug_1(x1) cout << #x1 << ": " << x1 << endl #define debug_2(x1, x2) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl #define debug_3(x1, x2, x3) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \ << x3 << endl #define debug_4(x1, x2, x3, x4) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \ << x3 << ", " #x4 << ": " << x4 << endl #define debug_5(x1, x2, x3, x4, x5) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \ << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl #ifdef _DEBUG #define debug(...) \ CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \ (__VA_ARGS__) #else #define debug(...) #endif istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } template istream &operator>>(istream &is, static_modint &a) { long long v; is >> v; a = v; return is; } template istream &operator>>(istream &is, dynamic_modint &a) { long long v; is >> v; a = v; return is; } template ostream &operator<<(ostream &os, const static_modint &a) { return os << a.val(); } template ostream &operator<<(ostream &os, const dynamic_modint &a) { return os << a.val(); } template istream &operator>>(istream &is, vector &v) { for (auto &e : v) is >> e; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (auto &e : v) os << e << ' '; return os; } template ostream &operator<<(ostream &os, const vector> &v) { for (auto &e : v) { for (auto &c : e) os << c << ' '; os << endl; } return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << "," << p.second; return os; } template ostream &operator<<(ostream &s, set P) { fore(it, P) { s << it << " "; } return s; } template ostream &operator<<(ostream &s, map P) { fore(x, y, P) { s << "<" << x << "->" << y << "> "; } return s; } template ostream &operator<<(ostream &s, multiset P) { fore(it, P) { s << it << " "; } return s; } template ostream &operator<<(ostream &s, unordered_set P) { fore(it, P) { s << it << " "; } return s; } template ostream &operator<<(ostream &s, unordered_map P) { fore(x, y, P) { s << "<" << x << "->" << y << "> "; } return s; } struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); }; } fast_ios_; vector iota(int n, int s = 0) { vi a(n); iota(a.begin(), a.end(), s); return a; } template void sort(vector &v) { sort(all(v)); } template void rsort(vector &v) { sort(rall(v)); } template void reverse(vector &v) { reverse(all(v)); } template auto min(const T &a) { return *min_element(all(a)); } template auto max(const T &a) { return *max_element(all(a)); } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } template vector uniq(vector v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v; } template vector compress(vector v) { vector v2(v.size()); v2 = v; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i = 0; i < v2.size(); i++) { v2[i] = lower_bound(v.begin(), v.end(), v2[i]) - v.begin(); } return v2; } template vector sumv(vector &v) { vector res(v.size()); for (int i = 0; i < v.size(); i++) { res[i] = i > 0 ? res[i - 1] + v[i] : v[0]; } return res; } template vector> sumv(vector> &v) { int h = v.size(), w = v[0].size(); cout << h << " " << w << el; vector> res(h, vector(w)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { res[i][j] = v[i][j]; if (i) res[i][j] += res[i - 1][j]; if (j) res[i][j] += res[i][j - 1]; if (i > 0 && j > 0) res[i][j] -= res[i - 1][j - 1]; } } return res; } template T exp(T x, ll n) { T res = 1; while (n > 0) { if (n & 1) res = res * x; x = x * x; n >>= 1; } return res; } constexpr ll ten(int n) { return n == 0 ? 1 : ten(n - 1) * 10; } long long ceil(long long x, long long y) { return (x + y - 1) / y; } void yesno(bool x) { if (x) { cout << "Yes" << endl; } else { cout << "No" << endl; } } int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1}; long long inf = 2000000000005000005; // using mint = static_modint<1000000009>; // using mint = dynamic_modint<1000000009>; // long long mod = 1000000007; // using mint = modint1000000007; // long long mod = 998244353; // using mint = modint998244353; // typedef vector vm; // typedef vector> vvm; // typedef vector>> vvvm; //////////////////////////////////////////////////////////////////////////////////////////// /* https://algo-logic.info/binary-indexed-tree/#toc_id_5_5 を参考に BIT: RAQ対応BIT 初期値は a_1 = a_2 = ... = a_n = 0 ・add(l,r,x): [l,r) に x を加算する ・sum(i): a_1 + a_2 + ... + a_i を計算する 計算量は全て O(logn) */ template struct BIT { int n; // 要素数 vector bit[2]; // データの格納先 BIT(int n_) { init(n_); } void init(int n_) { n = n_ + 1; for (int p = 0; p < 2; p++) bit[p].assign(n, 0); } void add_sub(int p, int i, T x) { for (int idx = i; idx < n; idx += (idx & -idx)) { bit[p][idx] += x; } } void add(int l, int r, T x) { // [l,r) に加算 add_sub(0, l, -x * (l - 1)); add_sub(0, r, x * (r - 1)); add_sub(1, l, x); add_sub(1, r, -x); } T sum_sub(int p, int i) { T s(0); for (int idx = i; idx > 0; idx -= (idx & -idx)) { s += bit[p][idx]; } return s; } T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; } }; /* https://github.com/drken1215/algorithm/blob/master/DataStructureOnTree/heavy_light_decomposition.cpp を参考に HLDecomposition hld(G):インスタンス生成 hld.build():HL木生成 foreach_nodes(u,v,function f):[u,v]間の頂点に対するクエリ foreach_edge(u,v,fucntion f):[u,v]間の辺に対するクエリ vid: id of v after HL-Decomposition inv: inv[vid[v]] = v par: id of parent depth subsize: size of subtree head: head-id in the heavy-path prev, next: prev-id, next-id in the heavy-path type: the id of tree for forest vend: the last-id of node in v-subtree */ typedef vector> Graph; struct HLDecomposition { int n; Graph G; vector vid, inv, par, depth, subsize, head, prev, next, type; // construct HLDecomposition() { } HLDecomposition(const Graph &G_) : n((int)G_.size()), G(G_), vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1), head(n), prev(n, -1), next(n, -1), type(n) { } void build(vector roots = {0}) { int curtype = 0, pos = 0; for (auto r : roots) decide_heavy_edge(r), reconstruct(r, curtype++, pos); } void decide_heavy_edge(int r) { stack> st; par[r] = -1, depth[r] = 0; st.emplace(r, 0); while (!st.empty()) { int v = st.top().first; int &i = st.top().second; if (i < (int)G[v].size()) { int e = G[v][i++]; if (e == par[v]) continue; par[e] = v, depth[e] = depth[v] + 1; st.emplace(e, 0); } else { st.pop(); int maxsize = 0; for (auto e : G[v]) { if (e == par[v]) continue; subsize[v] += subsize[e]; if (maxsize < subsize[e]) maxsize = subsize[e], prev[e] = v, next[v] = e; } } } } void reconstruct(int r, int curtype, int &pos) { stack st({r}); while (!st.empty()) { int start = st.top(); st.pop(); for (int v = start; v != -1; v = next[v]) { type[v] = curtype; vid[v] = pos++; inv[vid[v]] = v; head[v] = start; for (auto e : G[v]) if (e != par[v] && e != next[v]) st.push(e); } } } // node query [u, v], f([left, right]) void foreach_nodes(int u, int v, const function &f) { while (true) { 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; } } // edge query [u, v], f([left, right]) void foreach_edges(int u, int v, const function &f) { while (true) { 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; } } } // LCA int lca(int u, int v) { while (true) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } }; //////////////////////////////////////////////////////////////////////////////////////////// signed main() { int n; cin >> n; vvi g(n); rep(i, n - 1) { int u, v; cin >> u >> v; u--; v--; g[u].pb(v); g[v].pb(u); } HLDecomposition hl(g); hl.build(); BIT bit(n + 5); int ans = 0; int q; cin >> q; rep(q) { int a, b; cin >> a >> b; a--; b--; hl.foreach_nodes(a, b, [&](int l, int r) { bit.add(l + 1, r + 2, 1); ans += bit.sum(r + 1) - bit.sum(l); }); } cout << ans << el; }