#include #include #include #include #include #define llint long long using namespace std; typedef pair P; struct HLD{ int V, logV; vector

mp; map mp2; vector

parent; //subtree of v is [pre_order[v], back_order[v]] vector pre_order; vector back_order; int order; int global_id, local_id; vector size, depth; vector > prev; HLD(){} void predfs(vector G[], int v, int p, int d) { size[v] = 1, depth[v] = d, prev[v][0] = p; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == p) continue; predfs(G, G[v][i], v, d+1); size[v] += size[G[v][i]]; } } void maindfs(vector G[], int v, int p) { mp[v] = make_pair(global_id, local_id); mp2[make_pair(global_id, local_id)] = v; pre_order[v] = ++order; if(G[v].size() == 1 && G[v][0] == p){ back_order[v] = order; return; } vector

vec; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] == p) continue; vec.push_back(make_pair(size[G[v][i]], G[v][i])); } sort(vec.rbegin(), vec.rend()); local_id++; maindfs(G, vec[0].second, v); for(int i = 1; i < vec.size(); i++){ parent.push_back(mp[v]); global_id++, local_id = 0; maindfs(G, vec[i].second, v); } back_order[v] = order; } int getLCA(int u, int v){ int x = u, y = v; if(depth[y] > depth[x]) swap(x, y); for(int i = logV-1; i >= 0; i--){ if(depth[x] - (1<= depth[y]) x = prev[x][i]; } if(x == y) return x; for(int i = logV-1; i >= 0; i--){ if(prev[x][i] != prev[y][i]){ x = prev[x][i]; y = prev[y][i]; } } x = prev[x][0]; return x; } void pathcalc(int v, int lca, vector > &dest) { int gid = mp[v].first, lid = mp[v].second; int Gid = mp[lca].first, Lid = mp[lca].second; while(Gid != gid){ dest.push_back(make_pair(gid, make_pair(0, lid))); int ngid = parent[gid].first, nlid = parent[gid].second; gid = ngid, lid = nlid; } dest.push_back(make_pair(gid, make_pair(Lid, lid))); } void init(vector G[], int V) // The tree must be 1-indexed. { this->V = V, logV = 0; for(int t = V; t; t/=2) logV++; prev.resize(V+1); for(int i = 0; i <= V; i++) prev[i].resize(logV); size.resize(V+1), depth.resize(V+1); predfs(G, 1, 0, 0); prev[0][0] = 0; for(int i = 1; i < logV; i++){ for(int j = 1; j <= V; j++){ prev[j][i] = prev[prev[j][i-1]][i-1]; } } mp.resize(V+1), mp2.clear(); parent.clear(), parent.push_back(make_pair(-1, -1)); pre_order.resize(V+1), back_order.resize(V+1); global_id = local_id = 0, order = 0; maindfs(G, 1, 0); } void path(int u, int v, vector > &dest) { dest.clear(); int lca = getLCA(u, v); pathcalc(u, lca, dest); pathcalc(v, lca, dest); pair p = make_pair(mp[lca].first, make_pair(mp[lca].second, mp[lca].second)); for(int i = 0; i < dest.size(); i++){ if(dest[i] == p){ dest.erase(dest.begin()+i); return ; } } } void toOrder(vector > &src, vector

&dest) { dest.clear(); for(int i = 0; i < src.size(); i++){ int u = mp2[make_pair(src[i].first, src[i].second.first)], v = mp2[make_pair(src[i].first, src[i].second.second)]; dest.push_back(make_pair(pre_order[u], pre_order[v])); } } }; // range-add, range-min query struct SegTree{ int size; vector seg, delay; SegTree(){} SegTree(int size){ this->size = size; seg.resize(1<<(size+1)); delay.resize(1<<(size+1)); } void init() { for(int i = 0; i < (1<<(size+1)); i++){ seg[i] = 0; delay[i] = 0; } } void eval(int l, int r, int k) { if(delay[k]){ seg[k] += delay[k] * (r-l+1); if(l < r){ delay[k*2] += delay[k]; delay[k*2+1] += delay[k]; } delay[k] = 0; } } void update(int i, llint val) { i += (1 << size); seg[i] = val; while(i > 1){ i /= 2; seg[i] = seg[i*2] + seg[i*2+1]; } } void add(int a, int b, int k, int l, int r, llint val) { eval(l, r, k); if(b < l || r < a) return; if(a <= l && r <= b){ delay[k] += val; eval(l, r, k); return; } add(a, b, k*2, l, (l+r)/2, val); add(a, b, k*2+1, (l+r)/2+1, r, val); seg[k] = seg[k*2] + seg[k*2+1]; } void add(int a, int b, llint val){ if(a > b) return; add(a, b, 1, 0, (1< G[100005]; HLD hld; SegTree seg(17); int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; int u, v; for(int i = 1; i <= n-1; i++){ cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } hld.init(G, n); seg.add(1, n, 1); cin >> Q; llint ans = 0; for(int q = 0; q < Q; q++){ cin >> u >> v; vector > vec; vector

vec2; hld.path(u, v, vec); hld.toOrder(vec, vec2); for(int i = 0; i < vec2.size(); i++){ ans += seg.query(vec2[i].first, vec2[i].second); } for(int i = 0; i < vec2.size(); i++){ seg.add(vec2[i].first, vec2[i].second, 1); } } cout << ans << endl; return 0; }