#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LEN(x) (long long)(x.size()) #define FOR(i, a, n) for(int i=(a);i<(n); ++i) #define FOE(i, a) for(auto i : a) #define ALL(c) (c).begin(), (c).end() #define RALL(c) (c).rbegin(), (c).rend() #define BIT_COUNT32(bit) (__builtin_popcount(bit)) #define BIT_COUNT64(bit) (__builtin_popcountll(bit)) template using MinPriorityQueue = std::priority_queue, std::greater>; template using MaxPriorityQueue = std::priority_queue; // @formatter:off typedef long long LL; typedef __int128_t LLL; template std::vector make_v(size_t a){return std::vector(a);} template auto make_v(size_t a, Ts... ts){ return std::vector(ts...))>(a,make_v(ts...));} // C++14 template typename std::enable_if::value==0>::type fill_v(T &t,const V &v){t=v;} template typename std::enable_if::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);} template inline T ceil(T a, T b) { assert(a >= 0 and b > 0); return (a + b - 1) / b; } void print() { std::cout << std::endl; } template void print(Head&& head, Tail&&... tail) { std::cout << head; if (sizeof...(tail) != 0) {std::cout << " ";} print(std::forward(tail)...); } template void print(std::vector &v) {for (auto& a : v) { std::cout << a; if (&a != &v.back()) {std::cout << " ";} }std::cout << std::endl;} template void print(std::pair &p) { std::cout << p.first << " " << p.second << std::endl; } void debug() { std::cerr << std::endl; } template void debug(Head&& head, Tail&&... tail) { std::cerr << head; if (sizeof...(tail) != 0) {std::cerr << " ";} debug(std::forward(tail)...); } template void debug(std::vector &v) {for (auto& a : v) { std::cerr << a; if (&a != &v.back()) {std::cerr << " ";} }std::cerr << std::endl;} template void debug(std::pair &p) { std::cerr << p.first << " " << p.second << std::endl; } inline bool inside(long long y, long long x, long long H, long long W) {return 0 <= y and y < H and 0 <= x and x < W; } template inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } template inline T euclidean_distance2(T y1, T x1, T y2, T x2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } template inline T manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); } template T &chmin(T &a, const T &b) { return a = std::min(a, b); } template T &chmax(T &a, const T &b) { return a = std::max(a, b); } bool is_bit_on(const unsigned long long bit, const unsigned int i) { return (bit >> i) & 1u; } unsigned long long get_bit_set(const unsigned long long bit, const unsigned int i, const unsigned int b) { assert(b == 0 or b == 1); if (b == 0) { return bit & ~(1ull << i); } else {return bit | (1ull << i);}} // 初項s交差d長さnの数列の和 long long sum_of_arithmetic_progression(long long s, long long d, long long n) { return n * (2 * s + (n - 1) * d) / 2; } // 三角数 long long triangular_number(long long n) { return n * (n + 1) / 2; } // sqrt(x)の整数解を求める // 整数解がなければ-1 long long sqrt_integer(const long long x) { if (x < 0) { return -1; } auto a = (long long)sqrt(x); if (a * a == x) { return a; } if((a - 1) * (a - 1) == x) { return a - 1; } if((a + 1) * (a + 1) == x) { return a + 1; } return -1; } // xが2の階乗かどうか判定 bool is_power_of_two(long long x) { return !(x & (x - 1)); } // O(log max(a, b)) long long gcd(long long a, long long b) { if (b == 0) { return a; } return gcd(b, a % b); } long long lcm(long long a, long long b) { long long g = gcd(a, b); return a / g * b; } const int INF = 1u << 29u; // 536,870,912 const long long LINF = 1ull << 60u; const double EPS = 1e-9; const long double PI = acos(-1.0); // 2次元配列上での移動.右,下,左,上,右上,右下,左下,左上 const std::vector dy8 = {0, 1, 0, -1, -1, 1, 1, -1}, dx8 = {1, 0, -1, 0, 1, 1, -1, -1}; // @formatter:on template class Edge { public: int from; int to; T w; int no; Edge() : from(-1), to(-1), w(-1), no(-1) {} Edge(int from, int to, T w = 1, int no = -1) : from(from), to(to), w(w), no(no) { } }; template class Tree { private: bool build_done = false; public: const int num_nodes; std::vector>> graph; std::vector parent; std::vector>> children; explicit Tree(const int num_nodes) : num_nodes(num_nodes), graph(num_nodes) { } void add_directed_edge(const int u, const int v, const T w = 1, const int no = -1) { this->graph[u].emplace_back(Edge(u, v, w, no)); } void add_undirected_edge(const int u, const int v, const T w = 1, const int no = -1) { this->graph[u].emplace_back(Edge(u, v, w, no)); this->graph[v].emplace_back(Edge(v, u, w, no)); } std::vector> &operator[](const int u) { return this->graph[u]; } // 各ノードについて,親と子供を求める void build(const int root) { if (not this->build_done) { this->parent.resize(this->num_nodes, -1); this->children.resize(this->num_nodes); this->dfs(root, -1); } this->build_done = true; } private: void dfs(const int u, const int p) { this->parent[u] = p; for (auto e: this->graph[u]) { if (e.to != p) { this->children[u].emplace_back(e); this->dfs(e.to, u); } } } }; template class HeavyLightDecomposition { public: Tree tree; std::vector num_children; std::vector depth; std::vector hld; std::vector hld_index;// ノードが対応する hld のインデックス std::vector top; // 連結成分のうち最も浅い頂点 std::vector in, out; HeavyLightDecomposition(const Tree &tree) : tree(tree), num_children(tree.num_nodes), depth(tree.num_nodes), hld_index(tree.num_nodes), top(tree.num_nodes), in(tree.num_nodes), out(tree.num_nodes) { } void build(const int root) { this->tree.build(root); this->dfs(root, 0); this->heavy_light_decomposition(root, root); } // hld の index が対応する木の頂点番号 int idx_node(const int i) const { return this->hld[i]; } // u が対応する hld の index int node_idx(int u) const { return this->hld_index[u]; } // 頂点 u を根とする部分木が対応する hld の区間(半開区間) std::pair subtree_query(const int u) const { return {this->in[u], this->out[u]}; } // u から v までが対応する hld の区間の集合(半開区間) // クエリの個数は O(log N) // 辺の情報を扱うときは,u の親への辺の情報をノード u にいれるが, // path_queries では,lca(u, v)の親への辺の情報も含まれてしまうのでこの分を引く必要があることに注意 std::vector> path_queries(int u, int v) const { std::vector> ret; while (this->top[u] != this->top[v]) { if (this->depth[this->top[u]] <= this->depth[this->top[v]]) { ret.emplace_back(this->hld_index[this->top[v]], this->hld_index[v] + 1); v = this->tree.parent[this->top[v]]; } else { ret.emplace_back(this->hld_index[this->top[u]], this->hld_index[u] + 1); u = this->tree.parent[this->top[u]]; } } ret.emplace_back(std::min(this->hld_index[u], this->hld_index[v]), std::max(this->hld_index[u], this->hld_index[v]) + 1); return ret; } // u と v の最小共通祖先 // O(log N) int lca(int u, int v) const { while (u != v) { if (this->top[u] == this->top[v]) { break; } if (this->depth[this->top[u]] > this->depth[this->top[v]]) { u = this->tree.parent[this->top[u]]; } else { v = this->tree.parent[this->top[v]]; } } if (this->depth[u] < this->depth[v]) { return u; } return v; } private: int time = 0; // 各頂点について,深さ,その頂点を根とする部分木のサイズを求める int dfs(const int u, const int d) { this->num_children[u] = 1; this->depth[u] = d; for (const auto &edge: this->tree.children[u]) { this->num_children[u] += this->dfs(edge.to, d + 1); } return this->num_children[u]; } void heavy_light_decomposition(const int u, const int now_top) { this->hld_index[u] = this->hld.size(); this->hld.emplace_back(u); this->top[u] = now_top; this->in[u] = time++; if (this->tree.children[u].size() == 0) { this->out[u] = time; return; } // heavy な辺を探す int idx = -1; { int maxi_num_children = 0; int i = 0; for (const auto &e: this->tree.children[u]) { if (this->num_children[e.to] > maxi_num_children) { maxi_num_children = this->num_children[e.to]; idx = i; } ++i; } } // heavy な辺に進む(light より先にもぐる必要がある) this->heavy_light_decomposition(this->tree.children[u][idx].to, now_top); // light な辺に進む int i = 0; for (const auto &e: this->tree.children[u]) { if (i != idx) { this->heavy_light_decomposition(e.to, e.to); } ++i; } this->out[u] = time; } }; //#include //#include // すべて 0-origin template class FenwickTree { public: const int n; std::vector v; // n: 要素数 explicit FenwickTree(const int n) : n(n) { this->v.assign(n + 1, 0); } // v[i] // O(log n) T access(const int i) const { return this->sum(i, i + 1); } // v[i] += x // O(log n) void add(int i, T x) { assert(i < this->n); while (i < this->n) { this->v[i] += x; i |= i + 1; } } // v[i] = x // O(log n) void update(int i, T x) { assert(i < this->n); const T now = this->access(i); this->add(i, x - now); } // sum(v[0, i)) // O(log n) T sum(int i) const { assert(0 <= i and i <= this->n); T s = 0; i -= 1; while (i >= 0) { s += this->v[i]; i = (i & (i + 1)) - 1; } return s; } // sum(v[left, right)) // O(log n) T sum(const int left, const int right) const { if (left >= right) { return 0; } return this->sum(right) - this->sum(left); } }; // 区間加算,区間和取得 // すべて 0-origin template class FenwickTreeRange { const int n; FenwickTree ft0, ft1; public: explicit FenwickTreeRange(const int n) : n(n), ft0(n + 1), ft1(n + 1) {} // v[i] // O(log n) T access(const int i) const { assert(0 <= i and i < this->n); return this->sum(i, i + 1); } // v[i] += x // O(log n) void add(const int i, const T x) { assert(0 <= i and i < this->n); this->add(i, i + 1, x); } // v[left, right) += x // O(log n) void add(const int left, const int right, const T x) { if (left == right) { return; } assert(0 <= left and left < right and right <= this->n); this->ft0.add(left, x); this->ft0.add(right, -x); this->ft1.add(left, -x * left); this->ft1.add(right, x * right); } // v[left, right) += x // 加算位置が n 以上の場合は 0 に戻って加算される // O(log n) void add_circle(long long left, long long right, const T x) { assert(left < right); const long long num_loop = (right - left) / this->n; this->add(0, this->n, x * num_loop); // ループで終わり if ((right - left) % this->n == 0) { return; } left %= this->n; right %= this->n; if (left < right) { this->add(left, right, x); } else { this->add(left, this->n, x); this->add(0, right, x); } } // sum(v[0, i)) // O(log n) T sum(const int i) const { assert(0 <= i and i <= this->n); return ft0.sum(i) * i + ft1.sum(i); } // sum(v[left, right)) // O(log n) T sum(const int left, const int right) const { assert(0 <= left and left < right and right <= this->n); return this->sum(right) - this->sum(left); } // sum(v[left, right)) // O(log n) T sum_circle(const int left, const int right) const { // TODO return 0; } void dump() { for (int i = 0; i < this->n; ++i) { if (i != 0) { std::cout << " "; } std::cout << this->access(i); } std::cout << std::endl; } }; using namespace std; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; Tree tree(N); for (int i = 0; i < N - 1; ++i) { int U, V; cin >> U >> V; U--; V--; tree.add_undirected_edge(U, V); } HeavyLightDecomposition hld(tree); hld.build(0); FenwickTreeRange ftr(N); ftr.add(0, N, 1); long long ans = 0; int Q; cin >> Q; for (int i = 0; i < Q; ++i) { int A, B; cin >> A >> B; A--; B--; for (const auto &[l, r]: hld.path_queries(A, B)) { ans += ftr.sum(l, r); } for (const auto &[l, r]: hld.path_queries(A, B)) { ftr.add(l, r, 1); } } cout << ans << endl; return 0; }