#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; typedef long long ll; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define repk(i, k, n) for (int i = k; i < (int)(n); i++) #define all(v) v.begin(), v.end() #define mod1 1000000007 #define mod2 998244353 #define mod3 100000007 #define vi vector #define vs vector #define vc vector #define vl vector #define vb vector #define vvi vector> #define vvc vector> #define vvl vector> #define vvb vector> #define vvvi vector>> #define vvvl vector>> #define pii pair #define pil pair #define pli pair #define pll pair #define vpii vector> #define vpll vector> #define vvpii vector>> #define vvpll vector>> template void debug(T e) { cerr << e << endl; } template void debug(vector &v) { rep(i, v.size()) { cerr << v[i] << " "; } cerr << endl; } template void debug(vector> &v) { rep(i, v.size()) { rep(j, v[i].size()) { cerr << v[i][j] << " "; } cerr << endl; } } template void debug(vector> &v) { rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; } } template void debug(set &st) { for (auto itr = st.begin(); itr != st.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(multiset &ms) { for (auto itr = ms.begin(); itr != ms.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(map &mp) { for (auto itr = mp.begin(); itr != mp.end(); itr++) { cerr << itr->first << " " << itr->second << endl; } } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << H << " "; debug_out(T...); } using mint = modint998244353; void debug_mint1(vector &vec) { for (int i = 0; i < vec.size(); i++) { cerr << vec[i].val() << " "; } cerr << endl; } void debug_mint2(vector> &vec) { for (int i = 0; i < vec.size(); i++) { for (int j = 0; j < vec[i].size(); j++) { cerr << vec[i][j].val() << " "; } cerr << endl; } } struct HLDecomp{ ll N; vector u; vector v; vector> graph; vector lsize; vector> paths; // 頂点群のパス vector> paths_e; // 辺群のパス vector ids; // その頂点がどの系列の何番目に属するか? vector prev; // 前の頂点に向かう頂点の情報 vector prev_e; // 前の頂点に向かう辺の情報 vector euler_tour; vector in_order; // option vector depth; HLDecomp(ll N_, vector &u_, vector &v_){ N = N_; u.resize(N - 1); v.resize(N - 1); rep(i, N - 1){ u[i] = u_[i]; } rep(i, N - 1){ v[i] = v_[i]; } graph.resize(N); rep(i, N - 1){ graph[u[i]].push_back(v[i]); graph[v[i]].push_back(u[i]); } } void dfs(vector &isvisited, ll v){ isvisited[v] = true; ll ret = 1; for (ll x: graph[v]){ if (isvisited[x]) continue; depth[x] = depth[v] + 1; dfs(isvisited, x); ret += lsize[x]; } lsize[v] = ret; return; } void calc_size(){ lsize.resize(N, 0); depth.resize(N, 0); vector isvisited(N, false); dfs(isvisited, 0); return; } void dfs2(vector &h_child, vector &isvisited, ll v){ isvisited[v] = true; euler_tour.push_back(v); if (h_child[v] != -1){ dfs2(h_child, isvisited, h_child[v]); } for (ll x: graph[v]){ if (x == h_child[v]) continue; if (isvisited[x]) continue; dfs2(h_child, isvisited, x); } return; } void prepare(){ calc_size(); prev.resize(N, -1); prev_e.resize(N, -1); paths.resize(N); paths_e.resize(N); ids.resize(N); in_order.resize(N); euler_tour.resize(0); vector h_child(N, -1); for (ll i = 0; i < N; i++){ ll max_cs = 0; ll max_id = -1; for (ll x: graph[i]){ if (lsize[x] < lsize[i]){ if (max_cs < lsize[x]){ max_cs = lsize[x]; max_id = x; } } } if (max_id != -1){ h_child[i] = max_id; } } for (ll i = 0; i < N - 1; i++){ if (lsize[u[i]] < lsize[v[i]]){ prev[u[i]] = v[i]; prev_e[u[i]] = i; } else{ prev[v[i]] = u[i]; prev_e[v[i]] = i; } } for (ll i = 0; i < N; i++){ if (lsize[i] == 1){ ll now = i; paths[i].push_back(i); ids[i] = make_pair(i, 0); while (prev[now] != -1){ if (h_child[prev[now]] != now){ break; } paths_e[i].push_back(prev_e[now]); paths[i].push_back(prev[now]); now = prev[now]; ids[now] = make_pair(i, paths[i].size() - 1); } } } vector isvisited(N, false); dfs2(h_child, isvisited, 0); rep(i, N){ in_order[euler_tour[i]] = i; } return; } ll lca_query(ll u, ll v){ ll now_u = u; ll now_v = v; while (true){ if (ids[now_u].first == ids[now_v].first){ if (ids[now_u].second <= ids[now_v].second){ return paths[ids[now_v].first][ids[now_v].second]; } else{ return paths[ids[now_u].first][ids[now_u].second]; } } else if (in_order[now_u] < in_order[now_v]){ now_v = prev[paths[ids[now_v].first].back()]; } else{ now_u = prev[paths[ids[now_u].first].back()]; } } } ll lca_dist(ll u, ll v){ ll lca_v = lca_query(u, v); return depth[u] + depth[v] - 2 * depth[lca_v]; } vector find_route(ll u, ll v){ vector ret; ll lca_v = lca_query(u, v); if (lca_v == u){ ret.push_back(make_pair(v, u)); } else if (lca_v == v){ ret.push_back(make_pair(u, v)); } else{ ll now_u = u; while (true){ if (ids[lca_v].first == ids[now_u].first){ ret.push_back(make_pair(now_u, lca_v)); break; } else{ ret.push_back(make_pair(now_u, paths[ids[now_u].first].back())); now_u = prev[paths[ids[now_u].first].back()]; } } ll now_v = v; while (true){ if (ids[lca_v].first == ids[now_v].first){ ret.push_back(make_pair(now_v, lca_v)); break; } else{ ret.push_back(make_pair(now_v, paths[ids[now_v].first].back())); now_v = prev[paths[ids[now_v].first].back()]; } } } return ret; } }; // 区間加算区間和の遅延セグ木 struct S{ ll val; ll size; }; S op(S a, S b){ return S{a.val + b.val, a.size + b.size}; } S e(){ return S{0, 0}; } S mapping(ll f, S x){ return S{x.val + f * x.size, x.size}; } ll composition(ll f, ll g){ return f + g; } ll id(){ return 0LL; } int main() { // HL 分解の verify ll N; cin >> N; vector x(N - 1); vector y(N - 1); rep(i, N - 1){ cin >> x[i] >> y[i]; x[i]--; y[i]--; } ll Q; cin >> Q; vector a(Q); vector b(Q); rep(i, Q){ cin >> a[i] >> b[i]; a[i]--; b[i]--; } HLDecomp hld(N, x, y); hld.prepare(); // debug(hld.depth); vector> paths = hld.paths; vector ids = hld.ids; vector> seg(N); for (ll i = 0; i < N; i++){ ll len = paths[i].size(); if (len > 0){ seg[i] = lazy_segtree(len); rep(j, len){ seg[i].set(j, S{1, 1}); } } } ll ans = 0; rep(i, Q){ vector rt = hld.find_route(a[i], b[i]); ll len = rt.size(); for (ll j = 0; j < len; j++){ ll id = ids[rt[j].first].first; ll left = ids[rt[j].first].second; ll right = ids[rt[j].second].second; if (left > right){ return 0; } ll len_id = paths[id].size(); if (left > len_id) return 0; if (right > len_id) return 0; // debug_out(id, left, right); if (len > 1 && j == len - 1){ ans += seg[id].prod(left, right).val; seg[id].apply(left, right, 1); } else{ ans += seg[id].prod(left, right + 1).val; seg[id].apply(left, right + 1, 1); } } // cout << ans << endl; } cout << ans << endl; }