#include "stdio.h" #define SIZE 10000 int NxN_E[SIZE][SIZE]; int N_N[SIZE][SIZE]; int N_E[SIZE][SIZE]; int E_ExE[SIZE*5000][4]; int a[SIZE], b[SIZE], tax[SIZE]; int e; int c; int taxsum = 0; int COMPLETE = 0; int stay[SIZE]; void expand_edge(); int find_edge(); void paytax(); void move_and_paytax(); int add_E_ExE(n1,n2,e1,e2){ E_ExE[++e][0]=n1; E_ExE[e][1]=n2; E_ExE[e][2]=e1; E_ExE[e][3]=e2; return e; } void add_N_E(n1,n2,edge){ N_E[n1][++N_E[n1][0]]=edge; N_E[n2][++N_E[n2][0]]=edge; } void add_NxN_E(n1,n2,edge){ NxN_E[n1][n2]=edge; NxN_E[n2][n1]=edge; } void add_N_N(n1,n2){ N_N[n1][++N_N[n1][0]]=n2; N_N[n2][++N_N[n2][0]]=n1; } int add_maps(n1,n2,e1,e2){ if (NxN_E[n1][n2]) return 0; if (n1 == n2) return 0; int edge = add_E_ExE(n1,n2,e1,e2); add_N_E(n1,n2,edge); add_NxN_E(n1,n2,edge); return edge; } int otherNode(edge,node){ if (node==E_ExE[edge][0]) return E_ExE[edge][1]; else return E_ExE[edge][0]; } int isLeaf(node){ if (N_N[node][0]==1) return 1; else return 0; } void push(int u, int v){ int i,j,m; int P = add_maps(u,v,0,0); add_N_N(u,v); if (!isLeaf(u)){ for (i=1;i<=N_E[u][0];i++){ add_maps(otherNode(N_E[u][i],u),v,N_E[u][i],P); if (!isLeaf(v)){ m=N_E[v][0]; for (j=1;j<=m;j++) add_maps(otherNode(N_E[u][i],u),otherNode(N_E[v][j],v),N_E[u][i],N_E[v][j]); } } } } int main(int argc, char** argv) { int i,j,n,u,v,q; scanf("%d", &n); for (i=1; i <= n-1; i++) { scanf("%d%d", &u, &v); push(u,v); } scanf("%d", &q); for (i=1; i<=q; i++) { scanf("%d%d",&a[i],&b[i]); move_and_paytax(a[i],b[i]); } printf("%d\n",taxsum); } void paytax(village) { taxsum += (++tax[(village)]); } void move_and_paytax(u,v) { int i; c = 0; int E=NxN_E[u][v]; expand_edge(u,v,E); stay[c++]=v; stay[c]=-1; paytax(stay[0]); for (i=1;stay[i]>0;i++){ paytax(stay[i]); } } void expand_edge(u,v,E){ int L,R,l,r,mid; if (u == E_ExE[E][0]){ l = u;r = v; L=E_ExE[E][2];R=E_ExE[E][3]; } else { l = v; r = u; L=E_ExE[E][3];R=E_ExE[E][2]; } mid=otherNode(L,l); if (R==0) { //leaf_edge if (l == u) stay[c++]=l; else stay[c++]=r; }else{ if (u==l){ expand_edge(l,mid,L); expand_edge(mid,r,R); }else{ expand_edge(r,mid,R); expand_edge(mid,l,L); } } }