#include #include #include #include #include #include #include #include #include #include #include #include #include #define getchar getchar_unlocked #define putchar putchar_unlocked #define _rep(_1, _2, _3, _4, name, ...) name #define rep2(i, n) rep3(i, 0, n) #define rep3(i, a, b) rep4(i, a, b, 1) #define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c)) #define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__) using namespace std; using i64 = long long; using u8 = unsigned char; using u32 = unsigned; using u64 = unsigned long long; using f80 = long double; int get_int() { int c, n; while ((c = getchar()) < '0'); n = c - '0'; while ((c = getchar()) >= '0') n = n * 10 + (c - '0'); return n; } class RootedTree { private: struct InputEdge { int from, to; }; template struct Range { struct Iterator { T& operator * () const { return *iter; } bool operator != (const Iterator& rhs) const { return iter != rhs.iter; } void operator ++ () { ++iter; } T* operator + (int i) const { return iter + i; } size_t operator - (const Iterator rhs) const { return iter - rhs.iter; } T* iter; }; Range(T* f, T* l) : first({f}), last({l}) {} T operator [] (int i) { return *(first + i); } size_t size() const { return last - first; } Iterator& begin() { return first; } Iterator& end() { return last; } Iterator first, last; }; public: RootedTree(int N, int M=0) : N(N), ofs(N + 1), par(N), vid(N), head(N), heavy(N), len(N) { if (M > 0) in.reserve(M); } Range operator [] (int u) { return Range(&edges[ofs[u]], &edges[ofs[u + 1]]); } void add_edge(int u, int v) { in.push_back({u, v}); } void build(int root) { init(), dfs(root), bfs(root); } int lca(int u, int v) const { for (; head[u] != head[v]; u = par[head[u]]) if (vid[u] < vid[v]) swap(u, v); return vid[u] > vid[v] ? v : u; } pair< vector, vector< pair > > signed_euler_tour(int root) { range.resize(N); tour.resize(2 * N); int id = 0; e_rec(root, id); return {tour, range}; } vector get_path(int u, int v) const { vector pu, pv; int s = 0; while (head[u] != head[v]) { if (vid[u] < vid[v]) swap(u, v), swap(pu, pv), s ^= 1; for (int w = par[head[u]]; u != w; u = par[u]) pu.push_back(u); } if (vid[u] < vid[v]) swap(u, v), swap(pu, pv), s ^= 1; for (; vid[u] != vid[v]; u = par[u]) pu.push_back(u); pu.push_back(u); if (s) swap(pu, pv); reverse(pv.begin(), pv.end()); for (auto& w : pv) pu.push_back(w); return pu; } int parent(int u) const { return par[u]; } vector get_order() const { vector order(N); for (int i = 0; i < N; ++i) order[vid[i]] = i; return order; } private: void e_rec(int u, int& id, int p=-1) { tour[id] = u; range[u].first = id++; for (auto& v : (*this)[u]) if (v != p) e_rec(v, id, u); tour[id] = ~u; range[u].second = id++; } void bfs(int root) { vector que(N); int qh = 0, qt = 0, id = 0; que[qt++] = root; for (; qh < qt; ) { int u = que[qh++]; for (int v = u; v >= 0; v = heavy[v]) { vid[v] = id++, head[v] = u; for (auto& w : (*this)[v]) if (w != par[v] && w != heavy[v]) que[qt++] = w; } len[u] = id - vid[u]; } } int dfs(int u, int p=-1) { int s = 1, best = 0, h = -1; par[u] = p; for (auto& v : (*this)[u]) if (v != p) { int c = dfs(v, u); if (c > best) best = c, h = v; s += c; } heavy[u] = h; return s; } void init() { edges.resize(2 * in.size()); for (auto& e : in) ofs[e.from + 1]++, ofs[e.to + 1]++; for (int i = 1; i <= N; ++i) ofs[i] += ofs[i - 1]; for (auto& e : in) edges[ofs[e.from]++] = e.to, edges[ofs[e.to]++] = e.from; for (int i = N; i > 0; --i) ofs[i] = ofs[i - 1]; ofs[0] = 0; } private: int N; vector in; vector ofs, edges; vector par, vid, head, heavy, len; vector< pair > range; vector tour; }; void solve() { int N; while (~scanf("%d", &N)) { auto g = RootedTree(N); rep(i, N - 1) { int u = get_int() - 1, v = get_int() - 1; g.add_edge(u, v); } g.build(0); vector cumu(N); int M = get_int(); rep(i, M) { int u = get_int() - 1, v = get_int() - 1; int lca = g.lca(u, v), p = g.parent(lca); cumu[u] += 1; cumu[v] += 1; cumu[lca] -= 1; if (p >= 0) cumu[p] -= 1; } auto order = g.get_order(); i64 ans = 0; rep(i, N) { int u = order[N - 1 - i], p = g.parent(u); ans += i64(cumu[u]) * (cumu[u] + 1) / 2;; if (p >= 0) cumu[p] += cumu[u]; } printf("%lld\n", ans); } } int main() { clock_t beg = clock(); solve(); clock_t end = clock(); fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC); return 0; }