#include using namespace std; // T0: 元の配列のモノイド // T1: T0に対する作用素モノイド template class BaseLinkCutTree { // T0上の演算、単位元 virtual T0 f0(T0, T0) = 0; const T0 u0; // T1上の演算、単位元 virtual T1 f1(T1, T1) = 0; const T1 u1; // T0に対するT1の作用 virtual T0 g(T0, T1) = 0; // 多数のt1(T1)に対するf1の合成 virtual T1 p(T1, int) = 0; struct Node { int cnt; T0 val, acc, u0; T1 lazy, u1; Node *left, *right, *par; Node(T0 value, T0 u0, T1 u1) : cnt(1), val(value), lazy(u1), acc(u0), u0(u0), u1(u1), left(nullptr), right(nullptr), par(nullptr) {} bool isRoot() { return (!par) || (par->left != this && par->right != this); } // スプレー木を反転させる }; void push(Node* t) { if (t->cnt < 0) { swap(t->left, t->right); if (t->left) t->left->cnt = -(t->left->cnt); if (t->right) t->right->cnt = -(t->right->cnt); t->cnt = -t->cnt; } if (t->lazy != u1) { t->val = g(t->val, p(t->lazy, 1)); t->acc = g(t->acc, p(t->lazy, t->cnt)); if (t->left) t->left->lazy = g(t->left->lazy, p(t->lazy, 1)); if (t->right) t->right->lazy = g(t->right->lazy, p(t->lazy, 1)); t->lazy = u1; } } void eval(Node* t) { bool flag = (t->cnt < 0); t->cnt = 1, t->acc = t->val; if (t->left) push(t->left), t->cnt += _abs(t->left->cnt), t->acc = f1(t->left->acc, t->acc); if (t->right) push(t->right), t->cnt += _abs(t->right->cnt), t->acc = f1(t->acc, t->right->acc); if (flag) t->cnt = -t->cnt; } vector nodes; inline static int _abs(int val) { return val & 0x7fffffff; } // 回転 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; } eval(p), eval(u), u->par = g; if (!g) return; if (g->left == p) g->left = u; if (g->right == p) g->right = u; eval(g); } // u を splay 木の根にする void splay(Node* u) { while (!(u->isRoot())) { Node *p = u->par, *gp = p->par; if (p->isRoot()) { // zig push(p), push(u); rotate(u, (u == p->left)); } else { push(gp), push(p), push(u); 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); } } } push(u); } Node* expose(Node* u) { Node* last = nullptr; for (Node* v = u; v; v = v->par) { splay(v); v->right = last; eval(v); last = v; } splay(u); return last; } bool connected(Node* u, Node* v) { expose(u), expose(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) { expose(u); // u と親の間に辺があるか // assert(u->left); u->left->par = nullptr, u->left = nullptr, eval(u); } Node* lca(Node* u, Node* v) { // u,v が同じ連結成分内にあるか // assert(connected(u, v)); expose(u); return expose(v); } void evert(Node* u) { expose(u), u->cnt = -(u->cnt); } int depth(Node* u) { expose(u); return _abs(u->cnt) - 1; } void update(Node* u, Node* v, const T1 x) { evert(u), expose(v); v->lazy = f1(v->lazy, x), push(v); } T0 query(Node* u, Node* v) { evert(u), expose(v); return v->acc; } public: BaseLinkCutTree(T0 u0, T1 u1) : u0(u0), u1(u1) {} int make_new_node(T0 v) { int idx = nodes.size(); nodes.push_back(new Node(v, u0, u1)); return idx; } // id1 と id2 が同じ木(連結成分)に属するか bool connected(int id1, int id2) { return connected(nodes[id1], nodes[id2]); } // 木(連結成分)の根 id1 の親を id2 にする void link(int id1, int id2) { return link(nodes[id1], nodes[id2]); } // id とその親の間の辺を削除する void cut(int id) { return cut(nodes[id]); } // id1 と id2 の LCA を求める int lca(int id1, int id2) { return lca(nodes[id1], nodes[id2])->id; } // 元の木の根を id にする void evert(int id) { return evert(nodes[id]); } // id の深さを求める int depth(int id) { return depth(nodes[id]); } // id1 と id2 の間にある頂点すべてに x を足す void update(int id1, int id2, T1 x) { return update(nodes[id1], nodes[id2], x); } // id1 と id2 の間にある頂点すべてのコストの総和を求める T0 query(int id1, int id2) { return query(nodes[id1], nodes[id2]); } }; template struct MinUpdateQuery : public BaseLinkCutTree { using BaseLinkCutTree::BaseLinkCutTree; MinUpdateQuery() : MinUpdateQuery(numeric_limits::max(), numeric_limits::min()) {} T0 f0(T0 x, T0 y) override { return min(x, y); } T1 f1(T1 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T0 g(T0 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T1 p(T1 x, int len) override { return x; } }; template struct SumAddQuery : public BaseLinkCutTree { using BaseLinkCutTree::BaseLinkCutTree; SumAddQuery() : SumAddQuery(0, 0) {} T0 f0(T0 x, T0 y) override { return x + y; } T1 f1(T1 x, T1 y) override { return x + y; } T0 g(T0 x, T1 y) override { return x + y; } T1 p(T1 x, int len) override { return x * len; } }; template struct MinAddQuery : public BaseLinkCutTree { using BaseLinkCutTree::BaseLinkCutTree; MinAddQuery() : MinAddQuery(numeric_limits::max(), 0) {} T0 f0(T0 x, T0 y) override { return min(x, y); } T1 f1(T1 x, T1 y) override { return x + y; } T0 g(T0 x, T1 y) override { return x + y; } T1 p(T1 x, int len) override { return x; } }; template struct SumUpdateQuery : public BaseLinkCutTree { using BaseLinkCutTree::BaseLinkCutTree; SumUpdateQuery() : SumUpdateQuery(0, numeric_limits::min()) {} T0 f0(T0 x, T0 y) override { return x + y; } T1 f1(T1 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T0 g(T0 x, T1 y) override { return y == numeric_limits::min() ? x : y; } T1 p(T1 x, int len) override { return x == numeric_limits::min() ? numeric_limits::min() : x * len; } }; template struct SumAffineQuery : public BaseLinkCutTree> { using T1 = pair; // first * x + second using BaseLinkCutTree::BaseLinkCutTree; SumAffineQuery() : SumAffineQuery(0, {1, 0}) {} T0 f0(T0 x, T0 y) override { return x + y; } T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; } T0 g(T0 x, T1 y) override { return y.first * x + y.second; } T1 p(T1 x, int len) override { return {x.first, x.second * len}; } // update(i, j, {a, b}); // [i, j)にax + bを作用 // update(i, j, {0, a}); // update // update(i, j, {1, a}); // 加算 // update(i, j, {a, 0}); // 倍 }; template struct MinmaxAffineQuery : public BaseLinkCutTree, pair> { using T0 = pair; // {min, max} using T1 = pair; // first * x + second using BaseLinkCutTree::BaseLinkCutTree; MinmaxAffineQuery() : MinmaxAffineQuery({numeric_limits::max(), -numeric_limits::max()}, {1, 0}) { } // TODO: _u1を使うとコンパイル通らない原因不明 T0 f0(T0 x, T0 y) override { return {min(x.first, y.first), max(x.second, y.second)}; } T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; } T0 g(T0 x, T1 y) override { T0 ret = {x.first * y.first + y.second, x.second * y.first + y.second}; if (y.first < 0) swap(ret.first, ret.second); return ret; } T1 p(T1 x, int len) override { return x; } // update(i, j, {a, b}); // [i, j)にax + bを作用 // update(i, j, {0, a}); // update // update(i, j, {1, a}); // 加算 // update(i, j, {a, 0}); // 倍 }; int main() { ios::sync_with_stdio(false); cin.tie(0); SumAddQuery lct; int n; cin >> n; for (int i = 0; i < n; i++) lct.make_new_node(0); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--, b--; lct.link(a, b); } int q; cin >> q; long long ans = 0; while (q--) { int a, b; cin >> a >> b; a--, b--; lct.update(a, b, 1); } for (int i = 0; i < n; i++) { int k = lct.query(i, i); ans += 1LL * k * (k + 1) / 2; } cout << ans << endl; }