#ifndef LOCAL #include using ll = long long; using uint = unsigned int; using ull = unsigned long long; using ld = long double; using i128 = __int128_t; using u128 = __uint128_t; namespace fastio { static constexpr int BUF_SIZE = 1 << 20; struct Pre { char num[10000][4]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i][j] = n % 10 | '0'; n /= 10; } } } } constexpr pre; static struct FastOutput { private: static constexpr int TMP_SIZE = 1 << 10; char tmp[TMP_SIZE]; char buf[BUF_SIZE]; size_t buf_pos = 0; template inline char* wt_integer(T x) { char* p = tmp + TMP_SIZE - 1; if (x == 0) { *--p = '0'; } else { bool is_negative = false; if (x < 0) { is_negative = true; x = -x; } while (x >= 10000) { memcpy(p -= 4, pre.num[x % 10000], 4); x /= 10000; } if (x >= 1000) { memcpy(p -= 4, pre.num[x], 4); } else if (x >= 100) { memcpy(p -= 3, pre.num[x] + 1, 3); } else if (x >= 10) { memcpy(p -= 2, pre.num[x] + 2, 2); } else { *--p = pre.num[x][3]; } if (is_negative) *--p = '-'; } return p; } template inline void wt_tuple(const T& t) { if constexpr (N < std::tuple_size::value) { if constexpr (N > 0) wt(' '); const auto x = std::get(t); wt(x); wt_tuple(t); } } public: inline void wt(char c) { buf[buf_pos++] = c; if (buf_pos == BUF_SIZE) flush(); } inline void wt(const char* s) { for (; *s != '\0'; s++) { wt(*s); } } inline void wt(const std::string& s) { for (char c : s) wt(c); } template inline std::enable_if_t> wt(const Tp& x) { std::ostringstream oss; oss << std::fixed << std::setprecision(16) << x; wt(oss.str()); } template inline std::enable_if_t> wt(const Tp& x) { wt(wt_integer(x)); } inline void wt(const __int128_t& x) { wt(wt_integer(x)); } inline void wt(const __uint128_t& x) { wt(wt_integer(x)); } template inline void wt(const std::pair& p) { wt(p.first); wt(' '); wt(p.second); } template inline void wt(const std::tuple& t) { wt_tuple(t); } template inline void wt(const std::array& a) { for (size_t i = 0; i < N; i++) { if (i) wt(' '); wt(a[i]); } } template inline void wt(const std::vector& x) { for (size_t i = 0; i < x.size(); i++) { if (i) wt(' '); wt(x[i]); } } inline void flush() { fwrite(buf, 1, buf_pos, stdout); buf_pos = 0; } ~FastOutput() { flush(); } } fastout; static struct FastInput { private: char buf[BUF_SIZE]; size_t buf_pos = 0; size_t size = 0; char cur = 0; inline char rd_char() { if (buf_pos >= size) { size = fread(buf, 1, BUF_SIZE, stdin); buf_pos = 0; buf[0] = (size == 0 ? -1 : buf[0]); } return cur = buf[buf_pos++]; } template inline void rd_integer(Tp& x) { x = Tp{}; if (skip_blanks()) { int sign = +1; if (cur == '-') { sign = -1; rd_char(); } do { x += x + (x << 3) + (cur & 15); } while (!is_blank(rd_char())); x *= sign; } } inline bool is_blank(char c) { return c <= ' '; } inline bool skip_blanks() { while (is_blank(cur) && cur != -1) { rd_char(); } return cur != -1; } template void rd_tuple(T& t) { if constexpr (N < std::tuple_size::value) { auto& x = std::get(t); rd(x); rd_tuple(t); } } public: inline void rd(char& c) { skip_blanks(); c = cur; } inline void rd(std::string& s) { if (skip_blanks()) { s.clear(); do { s += cur; } while (!is_blank(rd_char())); } } template inline auto rd(T& x) -> std::void_t::value>> { rd_integer(x); } inline auto rd(__int128_t& x) { rd_integer(x); } inline auto rd(__uint128_t& x) { rd_integer(x); } inline void rd(double& x) { std::string s; rd(s); x = std::stod(s); } inline void rd(long double& x) { std::string s; rd(s); x = std::stold(s); } template void rd(std::pair& p) { rd(p.first); rd(p.second); } template void rd(std::tuple& t) { rd_tuple(t); } template void rd(std::array& x) { for (auto& d : x) rd(d); } template void rd(std::vector& x) { for (auto& d : x) rd(d); } } fastin; inline void flush() { fastout.flush(); } void IN() {} template void IN(Head& head, Tails&... tails) { fastin.rd(head); IN(tails...); } template void print(const Last& last) { fastout.wt(last); } template void print(const Head& head, const Tails&... tails) { fastout.wt(head); fastout.wt(' '); print(tails...); } template void println(const Args&... args) { print(args...); fastout.wt('\n'); } } // namespace fastio using fastio::flush; using fastio::IN; using fastio::print; using fastio::println; #define INT(...) \ int __VA_ARGS__; \ IN(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ IN(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ IN(__VA_ARGS__) #define DBL(...) \ double __VA_ARGS__; \ IN(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ IN(name) #define VV(type, name, h, w) \ vector> name(h, vector(w)); \ IN(name) #define debug(...) (void(0)) #else #include "algo/debug.h" #endif template struct Edge { int from; int to; T cost; friend bool operator<(const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; } friend bool operator>(const Edge& lhs, const Edge& rhs) { return lhs.cost > rhs.cost; } }; template struct Graph : public Edge { int N, M; std::vector> G; std::vector> edges; Graph() : N(0), M(0) {} explicit Graph(int n) : N(n), M(0), G(n) {} int add(int from, int to, T cost = 1, bool is_dir = false) { assert(0 <= from && from < N); assert(0 <= to && to < N); edges.push_back({from, to, cost}); G[from].push_back(M); if (!is_dir) G[to].push_back(M); return M++; } const std::vector& operator[](int p) const { return G[p]; } std::vector& operator[](int p) { return G[p]; } }; template struct HeavyLightDecomposition { private: int N, k; std::vector sz, head, in, out, par, dep, vid; const Graph& G; int dfs_sz(int v, int p = -1) { sz[v] = 1; for (int id : G[v]) { const auto& e = G.edges[id]; int to = v ^ e.from ^ e.to; if (to == p) continue; dep[to] = dep[v] + 1; sz[v] += dfs_sz(to, v); } return sz[v]; } void dfs_hld(int v, int p = -1) { in[v] = k; vid[in[v]] = v; k++; par[v] = p; int best = -1, bnode = -1; for (const int id : G[v]) { const auto& e = G.edges[id]; int to = v ^ e.from ^ e.to; if (to == p) continue; if (sz[to] > best) { best = sz[to]; bnode = to; } } if (bnode != -1) { head[bnode] = head[v]; dfs_hld(bnode, v); } for (const int id : G[v]) { const auto& e = G.edges[id]; int to = v ^ e.from ^ e.to; if (to == p || to == bnode) continue; head[to] = to; dfs_hld(to, v); } out[v] = k; } public: HeavyLightDecomposition() = default; HeavyLightDecomposition(const Graph& g, int root = 0) : HeavyLightDecomposition(g, std::vector{root}) {} HeavyLightDecomposition(const Graph& g, const std::vector& roots) : G(g) { N = G.N; sz.assign(N, -1); dep.resize(N); for (int r : roots) dfs_sz(r); for (int i = 0; i < N; i++) if (sz[i] == -1) dfs_sz(i); k = 0; head.assign(N, -1); in.resize(N); out.resize(N); par.resize(N); vid.resize(N); for (int r : roots) { head[r] = r; dfs_hld(r); } for (int i = 0; i < N; i++) { if (head[i] == -1) { head[i] = i; dfs_hld(i); } } } int get(int p) const { return in[p]; } int depth(int p) const { return dep[p]; } int operator[](int p) const { return get(p); } int size(int p) const { return sz[p]; } int kth_anc(int v, int k) { while (v >= 0) { int u = head[v]; if (in[v] - k >= in[u]) return vid[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } return -1; } int jump(int u, int v, int d) { int l = lca(u, v); int d1 = dep[u] - dep[l]; if (d <= d1) return kth_anc(u, d); int d2 = d1 + dep[v] - dep[l]; if (d <= d2) return kth_anc(v, d2 - d); return -1; } std::pair subtree(int p) const { return {in[p], out[p]}; } int lca(int u, int v) const { while (head[u] != head[v]) { if (in[u] > in[v]) std::swap(u, v); v = par[head[v]]; } return in[u] > in[v] ? v : u; } std::vector> ascend(int u, int v) const { std::vector> res; while (head[u] != head[v]) { res.emplace_back(in[u], in[head[u]]); u = par[head[u]]; } if (u != v) res.emplace_back(in[u], in[v] + 1); return res; } std::vector> descend(int u, int v) const { std::vector> res = ascend(v, u); for (auto&& [a, b] : res) std::swap(a, b); std::reverse(res.begin(), res.end()); return res; } template void path_vertex(int u, int v, const F& f) const { path_vertex(u, v, f, f); } template void path_vertex(int u, int v, const F& f, const G& g) const { int l = lca(u, v); const auto func = [&](int a, int b) -> void { if (a <= b) f(a, b + 1); else g(b, a + 1); }; for (const auto& [a, b] : ascend(u, l)) func(a, b); func(in[l], in[l]); for (const auto& [a, b] : descend(l, v)) func(a, b); } template void path_edge(int u, int v, const F& f) const { return path_edge(u, v, f, f); } template void path_edge(int u, int v, const F& f, const G& g) const { int l = lca(u, v); const auto func = [&](int a, int b) -> void { if (a <= b) f(a, b + 1); else g(b, a + 1); }; for (const auto& [a, b] : ascend(u, l)) func(a, b); for (const auto& [a, b] : descend(l, v)) func(a, b); } }; #include using S = std::pair; S op(S a, S b) { return S{a.first + b.first, a.second + b.second}; } S e() { return S{0, 0}; } long long id() { return 0; } S mapping(long long f, S x) { return S{x.first + f * x.second, x.second}; } long long composition(long long f, long long g) { return f + g; } void solve() { using namespace std; INT(N); Graph G(N); for (int i = 1; i < N; i++) { INT(u, v); u--; v--; G.add(u, v); } HeavyLightDecomposition hld(G); atcoder::lazy_segtree seg(vector(N, S{0, 1})); long long ans = 0; INT(Q); while (Q--) { INT(a, b); a--; b--; auto f = [&](int a, int b) -> void { seg.apply(a, b, 1); ans += seg.prod(a, b).first; }; hld.path_vertex(a, b, f); } println(ans); } int main() { int T = 1; // std::cin >> T; while (T--) { solve(); } }