#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<auto&operator<<(ostream&o,pairp){return o<<"{"<auto&operator<<(ostream&o,sets){for(auto&e:s)o< auto&operator<<(ostream&o,priority_queueq){while(!q.empty())o<auto&operator<<(ostream&o,mapm){for(auto&e:m)o<auto&operator<<(ostream&o,vectorv){for(auto&e:v)o<void ashow(T t,A...a){cout< P; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vvi; typedef vector vvl; typedef vector

vp; typedef vector vd; typedef vector vs; const int MAX_N = 100005; template class LinkCutTree { public: struct node { int id, sz; T val, lazy, al; node *left, *right, *par; bool rev; node(int num) : id(num), val(1), lazy(id1), al(1), left(nullptr), right(nullptr), par(nullptr), rev(false){} static const T id1 = (T)0; static const T id2 = (T)0; void opr1(T& arg1, const T arg2) const { arg1 += arg2; } T opr2(const T arg1, const T arg2) const { return arg1 + arg2; } bool isRoot(){ return (!par) || (par->left != this && par->right != this); } //スプレー木を反転させる void push(){ if(lazy != id1){ opr1(val, lazy), al += lazy * sz; if(left) opr1(left->lazy, lazy); if(right) opr1(right->lazy, lazy); lazy = id1; } if(!rev) return; swap(left, right); if(left) left->rev = !(left->rev); if(right) right->rev = !(right->rev); rev = false; } void eval(){ sz = 1, al = val; if(left) left->push(), sz += left->sz, al = opr2(left->al, al); if(right) right->push(), sz += right->sz, al = opr2(al, right->al); } }; private: // 回転 void rotate(node* u, bool right){ node *p = u->par, *g = p->par; if(right){ if((p->left = u->right)) u->right->par = p; u->right = p, p->par = u; }else{ if((p->right = u->left)) u->left->par = p; u->left = p, p->par = u; } p->eval(), u->eval(), u->par = g; if(!g) return; if(g->left == p) g->left = u; if(g->right == p) g->right = u; g->eval(); } // u を splay 木の根にする void splay(node* u){ while(!(u->isRoot())){ node *p = u->par, *gp = p->par; if(p->isRoot()){ // zig p->push(), u->push(); rotate(u, (u == p->left)); }else{ gp->push(), p->push(), u->push(); bool flag = (u == p->left); if((u == p->left) == (p == gp->left)){ // zig-zig rotate(p, flag), rotate(u, flag); }else{ // zig-zag rotate(u, flag), rotate(u, !flag); } } } u->push(); } node* access(node* u){ node* last = nullptr; for(node* v = u; v; v = v->par){ splay(v); v->right = last; v->eval(); last = v; } splay(u); return last; } bool connected(node* u, node* v){ access(u), access(v); return u->par; } // u と v を結ぶ (v の preferred child を u とする.) void link(node* u, node* v){ // u, v が同じ連結成分にないか // assert(!connected(u, v)); evert(u), u->par = v; } // u とその親の間の辺を削除 void cut(node* u){ access(u); // u と親の間に辺があるか // assert(u->left); u->left->par = nullptr, u->left = nullptr, u->eval(); } node* lca(node* u, node* v){ // u,v が同じ連結成分内にあるか // assert(connected(u, v)); access(u); return access(v); } void evert(node* u){ access(u); u->rev = !(u->rev); } int depth(node* u){ access(u); return u->sz - 1; } void range(node* u, node* v, const T x){ evert(u), access(v); v->opr1(v->lazy, x); } T query(node* u, node* v){ evert(u), access(v); return v->al; } public: node** arr; LinkCutTree(int node_size){ arr = new node*[node_size]; for(int i = 0; i < node_size; i++){ arr[i] = new node(i); } } // id1 と id2 が同じ木(連結成分)に属するか bool connected(int id1, int id2){ return connected(arr[id1],arr[id2]); } // 木(連結成分)の根 id1 の親を id2 にする void link(int id1, int id2){ return link(arr[id1],arr[id2]); } // id とその親の間の辺を削除する void cut(int id){ return cut(arr[id]); } // id1 と id2 の LCA を求める int lca(int id1, int id2){ return lca(arr[id1],arr[id2])->id; } // 元の木の根を id にする void evert(int id){ return evert(arr[id]); } // id の深さを求める int depth(int id){ return depth(arr[id]); } // id1 と id2 の間にある頂点すべてに x を足す void range(int id1, int id2, T x){ return range(arr[id1], arr[id2], x); } // id1 と id2 の間にある頂点すべてのコストの総和を求める T query(int id1, int id2){ return query(arr[id1], arr[id2]); } }; #define getchar getchar_unlocked #define putchar putchar_unlocked inline int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } inline void out(int n) { short res[10], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar('\n'); } int main() { int n = in(); LinkCutTree lc(n); rep(i,n-1){ int u = in(), v = in(); lc.link(u-1, v-1); } int q = in(); ll ans = 0; rep(i,q){ int a = in(), b = in(); ans += lc.query(a-1, b-1); lc.range(a-1, b-1, 1); } cout << ans << "\n"; return 0; }