#include using namespace std;using ll=int_fast64_t;using ld=long double;constexpr ll INF=1LL<<60; void solve();int main(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<0?i<(ll)n:i>(ll)n;i+=d) template inline bool chmax(T &a,const T &b){if(a inline bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;} #ifdef DEBUG #include "memo/dump.hpp" #else #define dump(...) #endif template class LinkCutTree{ public: using T = typename M::T; using E = typename M::E; struct Node{ Node *left = nullptr, *right = nullptr, *parent = nullptr; T value, sum; E lazy = M::id; int size = 1; bool reverse = false; Node(){} Node(T value) : value(value), sum(value){} bool push(){ if(lazy != M::id){ value = M::act(lazy, value, 1); sum = M::act(lazy, sum, size); if(left) left->lazy = M::compose(left->lazy, lazy); if(right) right->lazy = M::compose(right->lazy, lazy); lazy = M::id; } if(reverse){ swap(left, right); if(left) left->reverse ^= true; if(right) right->reverse ^= true; reverse = false; return true; } return false; } void update(){ size = 1, sum = value; if(left) left->push(), size += left->size, sum = M::dot(left->sum, sum); if(right) right->push(), size += right->size, sum = M::dot(sum, right->sum); } }; private: Node* array; void rotate(Node* v, Node* p, bool d){ if(d){ p->left = v->right; if(v->right) v->right->parent = p; v->right = p; }else{ p->right = v->left; if(v->left) v->left->parent = p; v->left = p; } p->parent = v; p->update(); } void splay(Node* v){ vector path; vector direction; for(Node* u = v;; u = u->parent){ Node* p = u->parent; if(!p || (p->left != u && p->right != u)){ v->parent = p; break; } path.push_back(p); direction.push_back(u == p->left); } reverse(path.begin(), path.end()); reverse(direction.begin(), direction.end()); rep(i, path.size()) direction[i] ^= path[i]->push(); v->push(); while(path.size() >= 2){ Node* p = path.back(); path.pop_back(); Node* g = path.back(); path.pop_back(); bool dp = direction.back(); direction.pop_back(); bool dg = direction.back(); direction.pop_back(); if(dp == dg) rotate(p, g, dg), rotate(v, p, dp); else rotate(v, p, dp), rotate(v, g, dg); } if(!path.empty()){ Node* p = path.back(); path.pop_back(); bool d = direction.back(); direction.pop_back(); rotate(v, p, d); } } Node* expose(Node* v){ Node *prev = nullptr; for(Node* cur = v; cur; cur = cur->parent){ splay(cur); cur->right = prev; prev = cur; } splay(v); v->update(); return prev; } void evert(Node* v){expose(v); v->reverse ^= true;} Node* lca(Node* u, Node* v){expose(u); return expose(v);} void link(Node* u, Node* v){evert(u); u->parent = v;} void cut(Node* v){ expose(v); v->left->parent = nullptr, v->left = nullptr; v->update(); } bool is_connected(Node* u, Node* v){ if(u == v) return true; expose(u), expose(v); return u->parent; } int depth(Node* v){expose(v); return v->size - 1;} void act(Node* u, Node* v, E f){evert(u), expose(v), v->lazy = M::compose(v->lazy, f);} T sum(Node* u, Node* v){evert(u), expose(v); return v->sum;} public: LinkCutTree(const vector &A){ array = new Node[A.size()]; rep(i, A.size()) array[i] = Node(A[i]); } ~LinkCutTree(){delete[] array;} void evert(int i){evert(&array[i]);} int lca(int i, int j){return lca(&array[i], &array[j]) - array;} void link(int i, int j){link(&array[i], &array[j]);} void cut(int i){cut(&array[i]);} bool is_connected(int i, int j){return is_connected(&array[i], &array[j]);} int depth(int i){return depth(&array[i]);} void act(int i, int j, E f){act(&array[i], &array[j], f);} T sum(int i, int j){return sum(&array[i], &array[j]);} }; struct monoid{ using T = ll; using E = ll; static const T e = 0; static T dot(T x, T y){return x + y;} static E compose(E f, E g){return f + g;} static const E id = 0; static T act(E f, T x, int size){return x + f * size;} }; void solve(){ int N; cin >> N; vector A(N, 1); LinkCutTree tree(A); rep(_, N - 1){ int u, v; cin >> u >> v; u--, v--; tree.link(u, v); } ll ans = 0; int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; u--, v--; ans += tree.sum(u, v); tree.act(u, v, 1); } cout << ans << '\n'; }