#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; }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; Tree tree(N+1, N); tree.unite(0, N); for (int i = 0; i < N-1; i++) { int u, v; cin >> u >> v; u--; v--; tree.unite(u, v); } N++; tree.init(); vector cnt(N); vector d(N); for (int i = 0; i < N; i++) { d[tree.depth[i]].push_back(i); } int Q; cin >> Q; for (int i = 0; i < Q; i++) { int u, v; cin >> u >> v; u--; v--; int p = tree.lca(u, v); if (u == p || v == p) { if (v == p) swap(u, v); cnt[v]++; cnt[tree.parent[0][p]]--; } else { cnt[v]++; cnt[u]++; cnt[p]--; cnt[tree.parent[0][p]]--; } } ll ans = 0; for (int i = N-1; i >= 0; i--) { for (int v : d[i]) { ans += (cnt[v]+1)*cnt[v]/2; for (int u : tree.T[v]) { if (tree.depth[u] < tree.depth[v]) { cnt[u] += cnt[v]; } } } } cout << ans << endl; return 0; }