#include using namespace std; //************************************************************** // link-cut tree //************************************************************** struct node { node *parent = nullptr; node *lch = nullptr; node *rch = nullptr; bool reversed = false; int size = 1; long long sum = 1; long long val = 1; long long lazy = 0; }; int size(node *x) { if (x == nullptr) return 0; return x->size; } long long sum(node *x) { if (x == nullptr) return 0; return x->sum; } void update(node *x) { if (x == nullptr) return; x->size = 1 + size(x->lch) + size(x->rch); x->sum = x->val + sum(x->lch) + sum(x->rch); } void push(node *x) { if (x == nullptr) return; if (x->lazy == 0 && !x->reversed) return; for (node *y : { x->lch, x->rch }) if (y != nullptr) { y->reversed ^= x->reversed; y->sum += x->lazy * size(y); y->lazy += x->lazy; } if (x->reversed) swap(x->lch, x->rch); x->reversed = false; x->val += x->lazy; x->lazy = 0; update(x); } //************************************************************** // link-cut tree basic operation //************************************************************** enum { LEFT, RIGHT }; bool is_root(node *x) { return x->parent == nullptr || (x->parent->lch != x && x->parent->rch != x); } int parent_direction(node *x) { if (is_root(x)) return -1; return x->parent->rch == x ? LEFT : RIGHT; } void connect(node *child, node *parent, int dir) { if (parent != nullptr && dir != -1) { (dir == RIGHT ? parent->lch : parent->rch) = child; update(parent); } if (child != nullptr) child->parent = parent; } void raise(node *x) { node *y = x->parent; node *z = y->parent; int xdir = parent_direction(x); int ydir = parent_direction(y); connect(xdir == LEFT ? x->lch : x->rch, y, xdir); connect(y, x, xdir ^ 1); connect(x, z, ydir); } void splay(node *x) { push(x); while (!is_root(x)) { push(x->parent->parent); push(x->parent); push(x); if (is_root(x->parent)) { raise(x); } else if (parent_direction(x) == parent_direction(x->parent)) { raise(x->parent); raise(x); } else { raise(x); raise(x); } } update(x); } void expose(node *x) { node *rch = nullptr; for (node *y = x; y != nullptr; y = y->parent) { splay(y); y->rch = rch; rch = y; update(y); } splay(x); } void cut(node *x) { expose(x); x->lch->parent = nullptr; x->lch = nullptr; update(x); } void link(node *x, node *p) { expose(x); expose(p); connect(x, p, LEFT); } void evert(node *x) { expose(x); x->reversed = true; } int main() { int n; cin >> n; vector tr(n); for (int i = 0; i < n; i++) tr[i] = new node(); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); u--; v--; evert(tr[v]); link(tr[v], tr[u]); } long long ans = 0; int Q; cin >> Q; for (int ii = 0; ii < Q; ii++) { int u, v; scanf("%d %d", &u, &v); u--; v--; evert(tr[u]); expose(tr[v]); ans += sum(tr[v]); tr[v]->lazy++; } cout << ans << endl; }