#include #include #include #include #include #include typedef int32_t i32; typedef int64_t i64; #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define ABS(a) ((a)>(0)?(a):-(a)) #define ALLOC(size,type) ((type*)calloc((size),sizeof(type))) #define SORT(a,num,cmp) qsort((a),(num),sizeof(*(a)),cmp) typedef struct directed_edge { int32_t vertex; int32_t next; } graph_edge; typedef struct directedGraph { graph_edge *edge; int32_t *start; int32_t pointer; int32_t vertex_num; int32_t edge_max_size; } graph; graph* new_graph (const int vertex_num) { graph *g = (graph *) calloc (1, sizeof (graph)); g->edge = (graph_edge *) calloc (1, sizeof (graph_edge)); g->start = (int32_t *) calloc (vertex_num, sizeof (int32_t)); g->pointer = 0; g->vertex_num = vertex_num; g->edge_max_size = 1; for (int32_t i = 0; i < vertex_num; ++i) { g->start[i] = -1; } return g; } void free_graph (graph *g) { free (g->edge); free (g->start); free (g); return; } void clear_graph (graph *g) { g->pointer = 0; for (int32_t i = 0; i < g->vertex_num; ++i) { g->start[i] = -1; } } void add_edge (graph *g, int32_t from, int32_t to) { if (g->pointer == g->edge_max_size) { g->edge_max_size *= 2; g->edge = (graph_edge *) realloc (g->edge, sizeof (graph_edge) * g->edge_max_size); } g->edge[g->pointer] = (graph_edge) {to, g->start[from]}; g->start[from] = g->pointer++; } void BFS_graph (graph *g, int32_t src, i32 *q, i32 *parent) { uint8_t *used = (uint8_t *) calloc (g->vertex_num, sizeof (uint8_t)); int32_t front = 0; int32_t last = 0; used[src] = 1; q[last++] = src; while (front < last) { const int32_t v = q[front++]; for (int32_t p = g->start[v]; p != -1; p = g->edge[p].next) { const int32_t u = g->edge[p].vertex; if (!used[u]) { used[u] = 1; q[last++] = u; parent[u] = v; } } } free(used); } typedef struct LCA_node { i32 vertex; i32 depth; } LCA_node; static inline LCA_node min_lca_node (LCA_node a, LCA_node b) { return a.depth < b.depth ? a : b; } typedef struct lowest_common_ancestor { i32 *min_index; i32 *max_index; LCA_node *seg; i32 size; } LCA; LCA* build_LCA (const graph *g, const i32 root) { LCA *res = (LCA *) calloc (1, sizeof (LCA)); const i32 n = g->vertex_num; i32 *min_index = (i32 *) calloc (2 * n, sizeof (i32)); i32 *max_index = min_index + n; res->min_index = min_index; res->max_index = max_index; i32 size = 1; while (size < 2 * n - 1) size *= 2; res->size = size; res->seg = (LCA_node *) calloc (2 * size, sizeof (LCA_node)); LCA_node *a = res->seg + size; uint8_t *used = (uint8_t *) calloc (n, sizeof (uint8_t)); typedef struct operation { i32 t, v, d; } op; op *stack = (op *) calloc (2 * n, sizeof (op)); i32 top = 0; stack[top++] = (op) {0, root, 0}; i32 k = 0; while (top > 0) { op t = stack[--top]; if (t.t) { max_index[t.v] = k; a[k++] = (LCA_node) {t.v, t.d}; continue; } used[t.v] = 1; min_index[t.v] = max_index[t.v] = k; a[k++] = (LCA_node) {t.v, t.d}; for (i32 p = g->start[t.v]; p != -1; p = g->edge[p].next) { i32 u = g->edge[p].vertex; if (used[u]) continue; stack[top++] = (op) {1, t.v, t.d}; stack[top++] = (op) {0, u, t.d + 1}; } } for (i32 i = size - 1; i >= 1; --i) { res->seg[i] = min_lca_node (res->seg[2 * i], res->seg[2 * i + 1]); } free (used); free (stack); return res; } void free_LCA (LCA *s) { free (s->min_index); free (s->seg); free (s); } LCA_node query (LCA *s, i32 a, i32 b) { i32 l = s->min_index[a] < s->min_index[b] ? s->min_index[a] : s->min_index[b]; i32 r = (s->max_index[a] > s->max_index[b] ? s->max_index[a] : s->max_index[b]) + 1; LCA_node res = {-1, s->size}; for (l += s->size, r += s->size; l < r; l >>= 1, r >>= 1) { if (l & 1) res = min_lca_node (res, s->seg[l++]); if (r & 1) res = min_lca_node (res, s->seg[--r]); } return res; } void run (void) { i32 n; scanf ("%" SCNi32, &n); graph *g = new_graph (n); for (i32 i = 1; i < n; ++i) { i32 a, b; scanf ("%" SCNi32 "%" SCNi32, &a, &b); a--; b--; add_edge (g, a, b); add_edge (g, b, a); } i32 *q = ALLOC (2 * n, i32); i32 *parent = q + n; BFS_graph (g, 0, q, parent); LCA *lca = build_LCA (g, 0); i32 t; scanf ("%" SCNi32, &t); i32 *dp = ALLOC (n, i32); while (t--) { i32 a, b; scanf ("%" SCNi32 "%" SCNi32, &a, &b); a--; b--; i32 p = query (lca, a, b) . vertex; dp[a] += 1; dp[b] += 1; dp[p] -= 1; if (p != 0) { dp[parent[p]] -= 1; } } for (i32 i = n - 1; i > 0; --i) { i32 v = q[i]; dp[parent[v]] += dp[v]; } i64 ans = 0; for (i32 i = 0; i < n; ++i) { ans += (i64) dp[i] * (dp[i] + 1) / 2; } printf ("%" PRIi64 "\n", ans); } int main (void) { run(); return 0; }