package No300台; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { solver(); } static void solver() { Scanner sc = new Scanner(System.in); int n = sc.nextInt();// the num of vertices; edges = new ArrayList[n]; for (int i = 0; i < n; i++) { edges[i] = new ArrayList<>(); } for (int i = 0; i < n - 1; i++) { int u = sc.nextInt() - 1; int v = sc.nextInt() - 1; edges[u].add(v); edges[v].add(u); } init(n); accum = new long[n]; int q = sc.nextInt(); for (int i = 0; i < q; i++) { int a = sc.nextInt() - 1; int b = sc.nextInt() - 1; int lca = lca(a, b); accum[a]++; accum[b]++; accum[lca]--; if (parent[0][lca] != -1) { accum[parent[0][lca]]--; } } dfs(-1,0); System.out.println(sum); } static long sum; static long[] accum; static void dfs(int pre, int cur) { for (int v : edges[cur]) { if (v != pre) dfs(cur, v); } for (int v : edges[cur]) { if (v != pre) { accum[cur] += accum[v]; } } sum += accum[cur] * (accum[cur] + 1) / 2; } // Verified ABC014 D,yukicoder No363 static int MAX_LOG_V;// =(int)log2(MAX_V)+1 static int MAX_V; static int root;// 根ノードの番号 static int parent[][];// [MAX_LOG_V + 1][MAX_V] // parent[k][v] 2^k回親を辿ったときに到達する頂点(根を通り過ぎたときは-1) static int[] depth;// [MAX_V] 根からの深さ static ArrayList edges[]; static void init(int N) { // 変数の用意 MAX_V = N; MAX_LOG_V = (int) (Math.log(MAX_V) / Math.log(2)) + 1; root = 0; parent = new int[MAX_LOG_V + 1][MAX_V]; depth = new int[MAX_V]; // parent[0]とdepthを初期化する bfs(root, -1, 0); // parentを初期化する for (int k = 0; k < MAX_LOG_V; k++) { for (int v = 0; v < MAX_V; v++) { if (parent[k][v] < 0) { parent[k + 1][v] = -1; } else { parent[k + 1][v] = parent[k][parent[k][v]]; } } } } static class P { int parent; int me; int depth; P(int me, int parent, int depth) { this.me = me; this.parent = parent; this.depth = depth; } } // dfsだとstack over flow が怖いのでbfs static void bfs(int v, int p, int d) { ArrayDeque

q = new ArrayDeque

(); q.add(new P(v, p, d)); while (!q.isEmpty()) { P u = q.poll(); parent[0][u.me] = u.parent; depth[u.me] = u.depth; for (int i = 0; i < edges[u.me].size(); i++) { if (edges[u.me].get(i) != u.parent) q.add(new P(edges[u.me].get(i), u.me, u.depth + 1)); } } } static int lca(int u, int v) { // uとvの深さが同じになるまで親を辿る if (depth[u] > depth[v]) { int d = u; u = v; v = d; } // depth[v]-depth[u]>=2^kとなる最小のkを求める。 // つまりuをvと深さが同じか小さいぎりぎりのところまで親を辿る。 for (int k = 0; k < MAX_LOG_V; k++) { if ((((depth[v] - depth[u]) >> k) & 1) == 1) { v = parent[k][v]; } } if (u == v) return u; // uとvが衝突しないように辿る。 for (int k = MAX_LOG_V - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v] && parent[k][u] != -1 && parent[k][v] != -1) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }