package No300台; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Scanner; public class Main implements Runnable{ public static void main(String[] args) { new Thread(null, new Main(), "", 1024L * 1024 * 100).start(); } @Override public void run() { solver(); } static void solver() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); 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; } static int MAX_LOG_V; static int MAX_V; static int root; static int parent[][]; static int[] depth; 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]; bfs(root, -1, 0); 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; } } 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) { if (depth[u] > depth[v]) { int d = u; u = v; v = d; } 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; 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]; } }