1843D. Apple Tree

Combinatorics, dfs and similar, dp, math, trees, 1200, https://codeforces.com/problemset/problem/1843/D

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using vi = vector<int>;
using usi = unordered_set<int>;

#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

int read() {
    int x = 0, f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch)) {
        if (ch == '-')
            f *= -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar_unlocked();
    }
    return x * f;
}

vector<i64> dp;
vector<vi> graph;

void dfs(int u, int fa) {
    for (int v : graph[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
    if (!dp[u])
        dp[u] = 1;
}

void solve() {
    int n = read();
    dp.assign(n + 1, 0);
    graph.assign(n + 1, vi());
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1, 0);
    int q = read();
    while (q--) {
        int x = read(), y = read();
        cout << dp[x] * dp[y] << '\n';
    }
}

int main() {
    // cin.tie(nullptr)->sync_with_stdio(false);
    int t = read();
    while (t--) {
        solve();
    }
    return 0;
}