#include #include #include #include //#include #include #include #include #include #include //#include #include #include #include //#include #include //#include #include #include #include #include #include const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector vi; typedef vector vll; typedef pair pii; class Tree { public: Tree(int V, int root) : V(V), root(root) { T.resize(V); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V); depth.resize(V); } // uとvをつなぐ // lcaを求めることが主目的なので無向グラフとしている void unite(int u, int v) { T[u].push_back(v); T[v].push_back(u); } // initする // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ void init() { dfs(root, -1, 0); for (int k = 0; k+1 < MAXLOGV; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k+1][v] = -1; else parent[k+1][v] = parent[k][parent[k][v]]; } } } // uとvのlcaを求める int lca(int u, int v) const { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < MAXLOGV; k++) { if ((depth[v] - depth[u])>>k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV-1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // uとvの距離を求める // edgeを定義しないといけない時はこれじゃダメ int dist(int u, int v) const { int p = lca(u, v); return (depth[u]-depth[p]) + (depth[v]-depth[p]); } void dfs(int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int next : T[v]) { if (next != p) dfs(next, v, d+1); } } static const int MAXLOGV = 25; // グラフの隣接リスト表現 vector > T; // 頂点の数 int V; // 根ノードの番号 int root; // 親ノード vector parent[MAXLOGV]; // 根からの深さ vector depth; }; // 遅延評価つきセグメント木 // update: [l, r) の区間に値 v を一様に追加する // query: [l, r) の区間の和を求める struct ST { vector seg, lazy; int size; ST() {} ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(size * 2); lazy.resize(size * 2); } inline void push(int k, int l, int r) { if (lazy[k] != 0) { seg[k] += lazy[k] * (r - l); if (r - l > 1) { lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; } lazy[k] = 0; } } inline ll merge(ll x, ll y) { return x + y; } void update(int a, int b, ll v, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[k] += v; push(k, l, r); } else { update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r); seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]); } } void update(int a, int b, ll v) { return update(a, b, v, 0, 0, size); } ll query(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; ll x = query(a, b, k * 2 + 1, l, (l + r) / 2); ll y = query(a, b, k * 2 + 2, (l + r) / 2, r); return merge(x, y); } ll query(int a, int b) { return query(a, b, 0, 0, size); } }; class HeavyLightDecomposition { public: struct heavy_set { vector element; int depth; int parent_vertex; heavy_set(int v, int d, int par) : element(1, v), depth(d), parent_vertex(par) {} }; vector> G; vector S; vector subtree_size; vector set_index; vector ele_index; private: int get_subtree_size(int v, int p) { int& sz = subtree_size[v]; sz = 1; for (int ch : G[v]) if (ch != p) { sz += get_subtree_size(ch, v); } return sz; } void make_path(int v, int p, int set_id) { set_index[v] = set_id; ele_index[v] = S[set_id].element.size() - 1; int largest_child = -1, maxi = 0; for (int ch : G[v]) if (ch != p) { if (maxi < get_subtree_size(ch, v)) { maxi = subtree_size[ch]; largest_child = ch; } } for (int ch : G[v]) if (ch != p) { if (largest_child == ch) { S[set_id].element.push_back(ch); make_path(ch, v, set_id); } else { S.emplace_back(ch, S[set_id].depth + 1, v); make_path(ch, v, S.size() - 1); } } } void init(int root) { subtree_size.resize(G.size()); set_index.resize(G.size()); ele_index.resize(G.size()); S.emplace_back(root, 0, root); make_path(root, root, 0); subtree_size.clear(); } public: HeavyLightDecomposition(const vector>& G, int root = 0) : G(G) { init(root); } pair get_position(int v) { return pair(set_index[v], ele_index[v]); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector > G(N); Tree tree(N, 0); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); tree.unite(u, v); } tree.init(); HeavyLightDecomposition hld(G); vector seg; for (int i = 0; i < hld.S.size(); i++) { seg.emplace_back(hld.S[i].element.size()); } ll ans = 0; int Q; cin >> Q; while (Q--) { int u, v; cin >> u >> v; u--; v--; int lca = tree.lca(u, v); while (hld.get_position(v).first != hld.get_position(lca).first) { pii tmp = hld.get_position(v); seg[tmp.first].update(0, tmp.second+1, 1); ans += seg[tmp.first].query(0, tmp.second + 1); v = hld.S[tmp.first].parent_vertex; } while (hld.get_position(u).first != hld.get_position(lca).first) { pii tmp = hld.get_position(u); seg[tmp.first].update(0, tmp.second+1, 1); ans += seg[tmp.first].query(0, tmp.second + 1); u = hld.S[tmp.first].parent_vertex; } pii tu = hld.get_position(u), tv = hld.get_position(v); int mini = min(tu.second, tv.second), maxi = max(tu.second, tv.second); seg[tu.first].update(mini, maxi + 1, 1); ans += seg[tu.first].query(mini, maxi + 1); } cout << ans << endl; return 0; }