#include using namespace std; using ll = long long; using ld = long double; using u64 = uint64_t; using i128 = __int128_t; using u128 = __uint128_t; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; #define vv(type, name, h, w) vector> name(h, vector(w)) #define vvv(type, name, h, w, l) vector>> name(h, vector>(w, vector(l))) #define vvvv(type, name, a, b, c, d) vector>>> name(a, vector>>(b, vector>(c, vector(d)))) #define vvvvv(type, name, a, b, c, d, e) vector>>>> name(a, vector>>>(b, vector>>(c, vector>(d, vector(e))))) #define elif else if #define FOR1(a) for (long long _ = 0; _ < (long long)(a); _++) #define FOR2(i, n) for (long long i = 0; i < (long long)(n); i++) #define FOR3(i, l, r) for (long long i = l; i < (long long)(r); i++) #define FOR4(i, l, r, c) for (long long i = l; i < (long long)(r); i += c) #define FOR1_R(a) for (long long _ = (long long)(a) - 1; _ >= 0; _--) #define FOR2_R(i, n) for (long long i = (long long)(n) - 1; i >= (long long)(0); i--) #define FOR3_R(i, l, r) for (long long i = (long long)(r) - 1; i >= (long long)(l); i--) #define FOR4_R(i, l, r, c) for (long long i = (long long)(r) - 1; i >= (long long)(l); i -= (c)) #define overload4(a, b, c, d, e, ...) e #define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR_R(...) overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define FOR_in(a, A) for (auto a: A) #define FOR_each(a, A) for (auto &&a: A) #define FOR_subset(t, s) for(long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define all(x) x.begin(), x.end() #define len(x) int(x.size()) int popcount(int x) { return __builtin_popcount(x); } int popcount(uint32_t x) { return __builtin_popcount(x); } int popcount(long long x) { return __builtin_popcountll(x); } int popcount(uint64_t x) { return __builtin_popcountll(x); } // __builtin_clz(x)は最上位bitからいくつ0があるか. int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(uint32_t x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(uint64_t x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // 入力 void rd() {} void rd(char &c) { cin >> c; } void rd(string &s) { cin >> s; } void rd(int &x) { cin >> x; } void rd(uint32_t &x) { cin >> x; } void rd(long long &x) { cin >> x; } void rd(uint64_t &x) { cin >> x; } template void rd(vector &v) { for (auto& x:v) rd(x); } void read() {} template void read(H &h, T &... t) { rd(h), read(t...); } #define CHAR(...) \ char __VA_ARGS__; \ read(__VA_ARGS__) #define STRING(...) \ string __VA_ARGS__; \ read(__VA_ARGS__) #define INT(...) \ int __VA_ARGS__; \ read(__VA_ARGS__) #define U32(...) \ uint32_t __VA_ARGS__; \ read(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ read(__VA_ARGS__) #define U64(...) \ uint64_t __VA_ARGS__; \ read(__VA_ARGS__) #define VC(t, a, n) \ vector a(n); \ read(a) #define VVC(t, a, h, w) \ vector> a(h, vector(w)); \ read(a) //出力 void wt() {} void wt(const char c) { cout << c; } void wt(const string s) { cout << s; } void wt(int x) { cout << x; } void wt(uint32_t x) { cout << x; } void wt(long long x) { cout << x; } void wt(uint64_t x) { cout << x; } void wt(double x) { cout << fixed << setprecision(16) << x; } void wt(long double x) { cout << fixed << setprecision(16) << x; } template void wt(const vector v) { int n = v.size(); for (int i = 0; i < n; i++) { if (i) wt(' '); wt(v[i]); } } void print() { wt('\n'); } template void print(Head &&head, Tail &&... tail) { wt(head); if (sizeof...(Tail)) wt(' '); print(forward(tail)...); } ///////////////////////////////////////////////////////////////////////////////////////// template int bisect_left(const vector &A, T x) { auto idx = lower_bound(A.begin(), A.end(), x) - A.begin(); return idx; } template int bisect_right(const vector &A, T x) { auto idx = upper_bound(A.begin(), A.end(), x) - A.begin(); return idx; } long long min(long long a, long long b) { return a < b ? a : b; } template T min(vector A) { assert (A.size()); T S = A[0]; for (T a : A) S = min(a, S); return S; } template T max(vector A) { assert (A.size()); T S = A[0]; for (T a : A) S = max(a, S); return S; } template T add(T x, T y) { return x + y; } template bool chmin(T & x, T a) { return a < x ? (x = a, true) : false; } template bool chmax(T & x, T a) { return a > x ? (x = a, true) : false; } template T sum(vector A) { T S = 0; for (int i = 0; i < int(A.size()); i++) S += A[i]; return S; } uint64_t random_u64(uint64_t l, uint64_t r) { static std::random_device rd; static std::mt19937_64 gen(rd()); std::uniform_int_distribution dist(l, r); return dist(gen); } long long gcd(long long a, long long b) { while (a) { b %= a; if (b == 0) return a; a %= b; } return b; } long long lcm(long long a, long long b) { if (a * b == 0) return 0; return a * b / gcd(a, b); } long long pow_mod(long long a, long long r, long long mod) { long long res = 1, p = a % mod; while (r) { if ((r % 2) == 1) res = res * p % mod; p = p * p % mod, r >>= 1; } return res; } long long mod_inv(long long a, long long mod) { if (mod == 1) return 0; a %= mod; long long b = mod, s = 1, t = 0; while (1) { if (a == 1) return s; t -= (b / a) * s; b %= a; if (b == 1) return t + mod; s -= (a / b) * t; a %= b; } } long long Garner(vector Rem, vector Mod, int MOD) { assert (Rem.size() == Mod.size()); long long mod = MOD; Rem.push_back(0); Mod.push_back(mod); long long n = Mod.size(); vector coffs(n, 1); vector constants(n, 0); for (int i = 0; i < n - 1; i++) { long long v = (Mod[i] + Rem[i] - constants[i]) % Mod[i]; v *= mod_inv(coffs[i], Mod[i]); v %= Mod[i]; for (int j = i + 1; j < n; j++) { constants[j] = (constants[j] + coffs[j] * v) % Mod[j]; coffs[j] = (coffs[j] * Mod[i]) % Mod[j]; } } return constants[n - 1]; } long long Tonelli_Shanks(long long a, long long mod) { a %= mod; if (a < 2) return a; if (pow_mod(a, (mod - 1) / 2, mod) != 1) return -1; if (mod % 4 == 3) return pow_mod(a, (mod + 1) / 4, mod); long long b = 3; if (mod != 998244353) { while (pow_mod(b, (mod - 1) / 2, mod) == 1) { b = random_u64(2, mod - 1); } } long long q = mod - 1; long long Q = 0; while (q % 2 == 0) { Q++, q /= 2; } long long x = pow_mod(a, (q + 1) / 2, mod); b = pow_mod(b, q, mod); long long shift = 2; while ((x * x) % mod != a) { long long error = (((pow_mod(a, mod - 2, mod) * x) % mod) * x) % mod; if (pow_mod(error, 1 << (Q - shift), mod) != 1) { x = (x * b) % mod; } b = (b * b) % mod; shift++; } return x; } long long floor_div(long long a, long long b) { if (b < 0) a *= -1, b *= -1; if (a >= 0) return a / b; return -((-a + b - 1) / b); } long long ceil_div(long long a, long long b) { if (b < 0) a *= -1, b *= -1; if (a >= 0) return (a + b - 1) / b; return - ((-a) / b); } ///////////////////////////////////////////////////////////////////////////////////////// /* 検索するとき https://www.google.com/search?udm=14&q= -ai */ template struct lazysegtree { int size = 1, n, log = 0; T (*op)(T, T); T e; T (*mapping)(F, T); F (*composing)(F, F); F id; vector data; vector lazy; lazysegtree(int n, T (*op)(T, T), T e, T (*mapping)(F, T), F (*composing)(F, F), F id) : n(n), op(op), e(e), mapping(mapping), composing(composing), id(id) { while (size < n) { log++; size <<= 1; } data.resize(2 * size, e), lazy.resize(2 * size, id); } void set_array(vector A) { assert (size >= int(A.size())); for (int i = 0; i < int(A.size()); i++) data[size + i] = A[i]; for (int i = size - 1; i > 0; i--) update(i); } // 作用後の更新用の関数 void update(int k) { data[k] = op(data[k << 1], data[(k << 1) + 1]); } // 作用用の関数 void all_apply(int k, F f) { data[k] = mapping(f, data[k]); if (k < size) lazy[k] = composing(f, lazy[k]); } // 遅延伝播用の関数 void push(int k) { all_apply(k << 1, lazy[k]), all_apply((k << 1) + 1, lazy[k]); lazy[k] = id; } void set(int i, T x) { assert (0 <= i && i < n); i += size; for (int h = log; h > 0; h--) push(i >> h); data[i] = x; for (int h = 1; h < log + 1; h++) update(i >> h); } T get(int i) { assert (0 <= i && i < size); i += size; for (int h = log; h > 0; h--) push(i >> h); return data[i]; } // 区間積の取得 T prod(int l, int r) { assert (0 <= l && l <= r && r <= n); if (l == r) return e; // 根からO(logN)個の区間のnodeにlazyを伝播しながら行く. l += size, r += size; for (int i = log; i > 0; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } // 区間積の取得 T L = e, R = e; while (l < r) { if (l & 1) L = op(L, data[l]), l += 1; if (r & 1) R = op(data[r -= 1], R); l >>= 1, r >>= 1; } return op(L, R); } // 1点作用 void apply_point(int i, F f) { assert (0 <= i && i < size); i += size; for (int h = log; h > 0; h--) push(i >> h); data[i] = mapping(f, data[i]); for (int h = 1; h < log + 1; h++) update(i >> h); } // 区間作用 void apply(int l, int r, F f) { assert (0 <= l && l <= r && r <= size); if (l == r) return; // 根からO(logN)個の区間のnodeにlazyを伝播しながら行く. l += size, r += size; for (int i = log; i > 0; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } // O(logN)個の区間のnodeに作用, その子に伝播. int ll = l, rr = r; while (l < r) { if ((l & 1) == 1) all_apply(l, f), l++; if ((r & 1) == 1) all_apply(r -= 1, f); l >>= 1, r >>= 1; } // 根に向かってdataの更新 l = ll, r = rr; for (int i = 1; i < log + 1; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } return; } // 二分探索 int max_right(int l, function check) { assert (0 <= l && l <= n); assert (check(e)); if (l == n) return n; l += size; for (int i = log; i > 0; i--) push(l >> i); T sm = e; while (1) { while (l % 2 == 0) l >>= 1; if (!check(op(sm, data[l]))) { while (l < size) { push(l), l <<= 1; if (check(op(sm, data[l]))) sm = op(sm, data[l]), l += 1; } return l - size; } sm = op(sm, data[l]), l += 1; if ((l & -l) == l) break; } return n; } int min_left(int r, function check) { assert (0 <= r && r <= n); assert (check(e)); if (r == 0) return 0; r += size; for (int i = log; i > 0; i--) push((r - 1) >> i); T sm = e; while (1) { r -= 1; while (r > 1 && (r % 2)) r >>= 1; if (!check(op(data[r], sm))) { while (r < size) { push(r), r = 2 * r + 1; if (check(op(data[r], sm))) sm = op(data[r], sm), r -= 1; } return r + 1 - size; } sm = op(data[r], sm); if ((r & -r) == r) break; } return 0; } }; struct Heavy_Light_Decomposition { int N, root, idx = 0; vector> G; vector sub, depth, order, tout, head, parent; Heavy_Light_Decomposition(vector> & G, int root) : N(int(G.size())), root(root), G(G), sub(N, 0), depth(N, 0), order(N, -1), tout(N, -1), head(N, root), parent(N, -1) { dfs_size(root), dfs_HLD(root); } void dfs_size(int u) { sub[u] = 1; for (auto & v : G[u]) { if (v == parent[u]) { if (G[u].size() >= 2 && v == G[u][0]) swap(G[u][0], G[u][1]); else continue; } depth[v] = depth[u] + 1; parent[v] = u; dfs_size(v); sub[u] += sub[v]; if (sub[v] > sub[G[u][0]]) swap(G[u][0], v); } } void dfs_HLD(int u) { order[u] = idx; idx++; for (auto v : G[u]) { if (v == parent[u]) continue; head[v] = (G[u][0] == v ? head[u] : v); dfs_HLD(v); } tout[u] = idx; } int LCA(int u, int v) { while (head[u] != head[v]) { if (order[u] > order[v]) swap(u, v); v = parent[head[v]]; } if (depth[u] < depth[v]) return u; else return v; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[LCA(u, v)]; } // ascend, descend 両方とも u -> v のパスの通り掛け順を計算 vector> ascend(int u, int v) { if (u == v) return {}; vector> res; while (head[u] != head[v]) { res.push_back({order[u], order[head[u]]}); u = parent[head[u]]; } if (u != v) res.push_back({order[u], order[v] + 1}); return res; } vector> descend(int u, int v) { if (u == v) return {}; vector> res; while (head[u] != head[v]) { res.push_back({order[head[v]], order[v]}); v = parent[head[v]]; } if (u != v) res.push_back({order[u] + 1, order[v]}); reverse(all(res)); return res; } template void path_query(int u, int v, F & f, bool vertex = 0) { int lca = LCA(u, v); for (auto [a, b] : ascend(u, lca)) f(a + 1, b); if (vertex) f(order[lca], order[lca] + 1); for (auto [a, b] : descend(lca, v)) f(a, b + 1); } template void subtree_query(int u, F & f, bool vertex = 0) { f(order[u] + int(!vertex), tout[u]); } }; struct mono { long long x, c; }; mono op(mono x, mono y) { return {x.x + y.x, x.c + y.c}; } mono e = {0, 0}; mono mapping(long long f, mono x) { return {x.x + f * x.c, x.c}; } void solve() { INT(N); vector> G(N); FOR(N - 1) { INT(u, v); u--, v--; G[u].push_back(v), G[v].push_back(u); } Heavy_Light_Decomposition HLD(G, 0); lazysegtree seg(N, op, e, mapping, add, 0); for (int i = 0; i < N; i++) seg.set(i, {1, 1}); long long ans = 0; auto f = [&](int l, int r) { ans += seg.prod(min(l, r), max(l, r)).x; seg.apply(min(l, r), max(l, r), 1); return; }; INT(Q); FOR(Q) { INT(u, v); u--, v--; HLD.path_query(u, v, f, 1); } print(ans); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int testcases = 1; //cin >> testcases; FOR(testcases) solve(); }