#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 + x->lazy * size(x); } 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; for (node *y : { x->lch, x->rch }) if (y != nullptr) { y->reversed ^= x->reversed; 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; 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); connect(x, z, ydir); update(y); update(x); update(z); } void splay(node *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); } } push(x); } void expose(node *x) { for (node *y = x, *rch = nullptr; 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); x->parent = p; p->rch = x; update(x); update(p); } void evert(node *x) { expose(x); x->rch = x->lch; x->lch = nullptr; if (x->rch != nullptr) x->rch->reversed ^= 1; update(x); } template void ignore_rch(node *x, F f) { node *rch = x->rch; x->rch = nullptr; update(x); f(); x->rch = rch; update(x); } node *tr[101010]; vector g[101010]; void dfs(int curr, int prev) { for (int next : g[curr]) if (next != prev) { link(tr[next], tr[curr]); dfs(next, curr); } } int main() { int n; cin >> 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--; g[u].push_back(v); g[v].push_back(u); } dfs(0, -1); long long ans = 0; int Q; cin >> Q; while (Q--) { int u, v; scanf("%d %d", &u, &v); u--; v--; evert(tr[u]); expose(tr[v]); ignore_rch(tr[v], [&]() { ans += sum(tr[v]); }); tr[v]->lazy++; } cout << ans << endl; }