Juan's Colorful Tree

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct PairHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

static inline uint64_t keyPair(int a, int b) {
    return (uint64_t(a) << 32) | uint32_t(b);
}

int main() {
    setIO();

    int T;
    cin >> T;
    while (T--) {
        int n, k, s, q;
        cin >> n >> k >> s >> q;

        vector<vector<int>> g(n + 1);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        vector<vector<int>> byColor(k + 1);
        for (int i = 0; i < s; i++) {
            int v, x;
            cin >> v >> x;
            byColor[x].push_back(v);
        }

        vector<pair<int, int>> queries(q);
        unordered_map<uint64_t, vector<int>, PairHash> ask;
        ask.reserve(size_t(2 * q + 10));
        ask.max_load_factor(0.7);

        for (int i = 0; i < q; i++) {
            int u, v;
            cin >> u >> v;
            queries[i] = {u, v};
            ask[keyPair(u, v)].push_back(i);
            if (u != v) ask[keyPair(v, u)].push_back(i);
        }

        int B = max(1, int(sqrt(s)) + 1);
        vector<int> ans(q, 0);
        vector<int> mark(n + 1, 0), comp(n + 1, 0), seen(n + 1, 0);
        int tag = 0, seenTag = 0;
        vector<int> st;

        for (int color = 1; color <= k; color++) {
            auto &nodes = byColor[color];
            if (nodes.empty()) continue;

            ++tag;
            for (int v : nodes) mark[v] = tag;

            if ((int)nodes.size() <= B) {
                ++seenTag;

                for (int start : nodes) {
                    if (seen[start] == seenTag) continue;

                    vector<int> cur;
                    st.clear();
                    st.push_back(start);
                    seen[start] = seenTag;

                    while (!st.empty()) {
                        int u = st.back();
                        st.pop_back();
                        cur.push_back(u);

                        for (int v : g[u]) {
                            if (mark[v] == tag && seen[v] != seenTag) {
                                seen[v] = seenTag;
                                st.push_back(v);
                            }
                        }
                    }

                    for (int a : cur) {
                        for (int b : cur) {
                            auto it = ask.find(keyPair(a, b));
                            if (it == ask.end()) continue;
                            for (int id : it->second) ans[id]++;
                        }
                    }
                }
            } else {
                int cid = 0;
                for (int v : nodes) comp[v] = 0;

                for (int start : nodes) {
                    if (comp[start]) continue;
                    ++cid;
                    st.clear();
                    st.push_back(start);
                    comp[start] = cid;

                    while (!st.empty()) {
                        int u = st.back();
                        st.pop_back();

                        for (int v : g[u]) {
                            if (mark[v] == tag && comp[v] == 0) {
                                comp[v] = cid;
                                st.push_back(v);
                            }
                        }
                    }
                }

                for (int i = 0; i < q; i++) {
                    auto [u, v] = queries[i];
                    if (mark[u] == tag && mark[v] == tag && comp[u] == comp[v]) ans[i]++;
                }
            }
        }

        for (int i = 0; i < q; i++) cout << ans[i] << ' ';
        cout << '\n';
    }

    return 0;
}