#include // clang-format off #include using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (n); i++) template inline bool chmax(T &a,const S &b) {return (a inline bool chmin(T &a,const S &b) {return (a>b? a=b,1:0);} using ll = long long; // clang-format on #ifdef LOCAL #include #else #define debug(...) static_cast(0) #endif /* Edge */ template struct Edge { int id; int from; int to; T cost; bool operator<(const Edge &other) const { return cost < other.cost; } bool operator>(const Edge &other) const { return cost > other.cost; } }; /* Graph */ template struct Graph { int _n; vector>> _graph; const T INF = numeric_limits::max() / 2; vector> _edges; // i番目に追加された辺をもつ Graph(int n) : _n(n) { _graph.resize(_n); } vector> &operator[](int i) { return _graph[i]; } int size() { return _n; } /* 頂点 u v 間に重さ cost の双方向の辺を張る */ void add_edge(int u, int v, T cost) { assert(0 <= u && u < _n); assert(0 <= v && v < _n); int id = (int)_edges.size(); _graph[u].push_back({id, u, v, cost}); _graph[v].push_back({id, v, u, cost}); _edges.push_back({id, u, v, cost}); } /* 頂点 from から 頂点 to に cost の有向辺を張る */ void add_edge_directed(int from, int to, T cost) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); int id = (int)_edges.size(); _graph[from].push_back({(int)_edges.size(), from, to, cost}); _edges.push_back({id, from, to, cost}); } /* 頂点 u v 間に重さ 1 の双方向の辺を張る */ void add_edge(int u, int v) { add_edge(u, v, 1); } /* 頂点 from から 頂点 to に重さ 1 の有向辺を張る */ void add_edge_directed(int from, int to) { add_edge_directed(from, to, 1); } /* i番目の辺を返す */ Edge getEdge(int i) { assert(0 <= i && i < (int)_edges.size()); return _edges[i]; } }; template struct HLD { private: void dfs_sz(int v) { auto &es = G[v]; if (~par[v]) es.erase(find(es.begin(), es.end(), par[v])); for (int &u : es) { par[u] = v; dfs_sz(u); sub[v] += sub[u]; if (sub[u] > sub[es[0]]) swap(u, es[0]); } } void dfs_hld(int v, int &pos) { vid[v] = pos++; inv[vid[v]] = v; for (int u : G[v]) { if (u == par[v]) continue; nxt[u] = (u == G[v][0] ? nxt[v] : u); dfs_hld(u, pos); } } public: int n; vector> G; vector vid, nxt, sub, par, inv; HLD(Graph _g, int root = 0) : n((int)_g.size()), vid(n, -1), nxt(n), sub(n, 1), par(n, -1), inv(n) { G.resize(n); for (int pos = 0; pos < n; pos++) { for (auto e : _g._graph[pos]) { G[pos].push_back(e.to); } } dfs_sz(root); nxt[root] = root; int pos = 0; dfs_hld(root, pos); } int lca(int u, int v) { while (true) { if (vid[u] > vid[v]) swap(u, v); if (nxt[u] == nxt[v]) return u; v = par[nxt[v]]; } } /* f の引数は半開区間 [l, r)*/ void query_each_nodes(int u, int v, const function &f) { while (true) { if (vid[u] > vid[v]) swap(u, v); f(max(vid[nxt[v]], vid[u]), vid[v] + 1); if (nxt[u] != nxt[v]) v = par[nxt[v]]; else break; } } /* f の引数は半開区間 [l, r) */ void query_each_edges(int u, int v, const function &f) { while (true) { if (vid[u] > vid[v]) swap(u, v); if (nxt[u] != nxt[v]) { f(vid[nxt[v]], vid[v] + 1); v = par[nxt[v]]; } else { if (u != v) f(vid[u] + 1, vid[v] + 1); break; } } } }; /* HLD (Heavy-Light Decomposition) vid: 頂点->id inv: id->頂点 nxt: HL分解後の連結成分内の最も小さい頂点 par: 頂点の親 query_for_nodes(u, v, f): パス上の各頂点に対するクエリに対応する. query_for_edges(u, v, f): パス上の全ての辺に対するクエリに対応する. f = [&](int l, int r) { *** } : 半開区間[l, r) に対する処理 1 / | 2 3 例) パス[1,2]の情報は、頂点2に持たせる */ // // 区間加算 & 区間和取得 // struct S { ll value; int size; }; using F = ll; S op(S a, S b) { return {a.value + b.value, a.size + b.size}; } S e() { return {0, 1}; } S mapping(F f, S x) { return {x.value + f * x.size, x.size}; } F composition(F f, F g) { return f + g; } F id() { return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; Graph G(n); lazy_segtree seg(n); rep(i, n - 1) { int u, v; cin >> u >> v; --u, --v; G.add_edge(u, v); } HLD hld(G); int Q; cin >> Q; while (Q--) { int a, b; cin >> a >> b; --a, --b; hld.query_each_nodes(a, b, [&](int l, int r) { seg.apply(l, r, 1); }); } ll ans = 0; rep(i, n) { ll x = seg.get(i).value; ans += x * (x + 1) / 2; } cout << ans << '\n'; return 0; }