#include #define PB push_back #define MP make_pair #define int long long int using namespace std; typedef pair PII; typedef pair PPI; typedef pair PIP; typedef pair PPP; typedef vector VP; typedef VP::iterator VPI; typedef vector VI; const int INF = 3e18; const double PI = acos(-1); int n, q; VI node[100001]; VI under[100001]; int a[100001], b[100001]; VP segarray; int segnum[100001]; int pluss[100001], minuss[100001]; int ans = 0; void input() { scanf("%lld", &n); for(int i = 1; i <= n - 1; i++){ int u, v; scanf("%lld%lld", &u, &v); node[u].PB(v); node[v].PB(u); } scanf("%lld", &q); for(int i = 0; i < q; i++){ scanf("%lld%lld", &a[i], &b[i]); } } void dfs(int parent, int x, int deep) { segnum[x] = segarray.size(); segarray.PB(MP(deep, x)); for(int i = 0; i < node[x].size(); i++){ if(node[x][i] != parent){ under[x].PB(node[x][i]); dfs(x, node[x][i], deep + 1); segarray.PB(MP(deep, x)); } } } struct segtree { PII tree[9000000]; int size; void reset() { size = 1; while(size < segarray.size()){ size <<= 1; } set(0, size - 1, 0); } PII set(int left, int right, int now) { if(left == right){ if(left >= segarray.size()){ return tree[now] = MP(INF, INF); } else{ return tree[now] = segarray[left]; } } else{ return tree[now] = min(set(left, (left + right) / 2, now * 2 + 1), set((left + right) / 2 + 1, right, now * 2 + 2)); } } PII smallest(int start, int end, int left, int right, int now) { if(right < start || end < left){ return MP(INF, INF); } if(start <= left && right <= end){ return tree[now]; } return min(smallest(start, end, left, (left + right) / 2, now * 2 + 1), smallest(start, end, (left + right) / 2 + 1, right, now * 2 + 2)); } } lcm; void compedge(int x) { int lcma = segnum[a[x]], lcmb = segnum[b[x]]; if(lcma > lcmb) swap(lcma, lcmb); PII lcmed = lcm.smallest(lcma, lcmb, 0, lcm.size - 1, 0); if(lcmed.second == a[x]){ pluss[b[x]]++; minuss[a[x]]--; } else if(lcmed.second == b[x]){ pluss[a[x]]++; minuss[b[x]]--; } else{ pluss[a[x]]++; pluss[b[x]]++; pluss[lcmed.second]--; minuss[lcmed.second]--; } } int sumdp[200000]; int calcsum(int now) { if(now == 0) return 0; if(sumdp[now] != -1) return sumdp[now]; return sumdp[now] = now + calcsum(now - 1); } int solve(int now) { int sum = 0; for(int i = 0; i < under[now].size(); i++){ sum += solve(under[now][i]); } sum += pluss[now]; ans += calcsum(sum); sum += minuss[now]; return sum; } signed main() { input(); dfs(0, 1, 0); lcm.reset(); for(int i = 0; i < q; i++){ compedge(i); } memset(sumdp, -1, sizeof sumdp); solve(1); printf("%lld\n", ans); return 0; }