你这份代码的瓶颈确实能在不改变根号算法的前提下解决。QOJ 时限只有 3.5 秒；题面给出的编译方式也是 -O2 -static，所以这里需要降低内存访问和间接寻址，而不只是加 pragma。(QOJ)

最大的几个常数问题

1. 不要在每一轮遍历 vector<int> adj[n]

根号部分最多约 $1000$ 轮。当前代码每轮执行：

cpp
for (int i = 0; i < n; i++)
    for (auto j : adj[i])

也就是反复访问 50 万个 vector 对象及其分散的堆内存。

DFS 序中父亲一定出现在儿子前面，只保留：

cpp
par[i] = 父亲的 DFS 序

即可计算下一层：

cpp
h[i] = g[par[i]] - f[i] * (deg[i] - 1);
h[par[i]] += g[i];

因为遍历到 i 时，h[par[i]] 已经初始化，所以初始化和向父亲贡献可以在同一个循环完成。

2. 删除 wsc 和 processed

设：

那么：

只需要：

cpp
cnt[i] += g[i];
lhs[i] += cnt[i];

判定条件就是：

cpp
lhs[i] >= n

而原来的距离和满足：

所以分子为：

cpp
n + cnt[i] * (d + 1) - lhs[i]

并且 lhs[i] >= n 本身就可以充当 processed 标记。

3. 你的 int h 存在有符号溢出 UB

例如某个高度数点上：

cpp
-f[i] * (deg[i] - 1)

可能达到 $O(n^2)$，虽然之后邻居贡献会把它抵消到 $[0,n]$，但中间的有符号溢出是未定义行为。

可以有意使用 uint32_t 模 $2^{32}$ 运算。线性递推在模意义下仍成立，而最终的距离层点数不超过 $n<2^{32}$，所以最终值就是正确值。

4. 不要重建第二份邻接表

第一次建树直接用 CSR 连续数组。得到 DFS 序、父亲和深度后，邻接表即可释放。根号部分只访问连续数组。

可直接提交的版本

仍然是你的：

做法，没有点分树和长链剖分。

cpp
#include <bits/stdc++.h>

std::vector<std::pair<long long, int>> teleport(
    int c,
    int n,
    int m,
    std::vector<int> u,
    std::vector<int> v,
    std::vector<int> x,
    std::vector<int> y
);

using namespace std;

namespace {

constexpr int kMaxN = 500000;
constexpr int kLog = 20;

alignas(64) int rmq[kLog][kMaxN];

}  // namespace

vector<pair<long long, int>> teleport(
    int c,
    int n,
    int m,
    vector<int> u,
    vector<int> v,
    vector<int> x,
    vector<int> y
) {
    (void)c;

    using U32 = uint32_t;
    using U64 = uint64_t;

    /*
     * 建立 CSR 邻接表。
     */
    vector<int> original_degree(n, 0);

    for (int i = 0; i < n - 1; ++i) {
        ++original_degree[u[i]];
        ++original_degree[v[i]];
    }

    vector<int> offset(n + 1, 0);

    for (int i = 0; i < n; ++i) {
        offset[i + 1] = offset[i] + original_degree[i];
    }

    vector<int> cursor = offset;
    vector<int> to(2 * n - 2);

    for (int i = 0; i < n - 1; ++i) {
        to[cursor[u[i]]++] = v[i];
        to[cursor[v[i]]++] = u[i];
    }

    vector<int>().swap(cursor);
    vector<int>().swap(original_degree);
    vector<int>().swap(u);
    vector<int>().swap(v);

    /*
     * 非递归 DFS，得到 DFS 序。
     *
     * 普通栈 DFS 仍然保证每棵子树在 DFS 序中连续，
     * 所以原代码的 preorder RMQ LCA 仍然适用。
     */
    vector<int> original_parent(n, -1);
    vector<int> original_depth(n, 0);
    vector<int> dfn(n);
    vector<int> order(n);
    vector<int> stack;

    stack.reserve(n);
    original_parent[0] = 0;
    stack.push_back(0);

    int timer = 0;

    while (!stack.empty()) {
        int a = stack.back();
        stack.pop_back();

        dfn[a] = timer;
        order[timer++] = a;

        for (int e = offset[a]; e < offset[a + 1]; ++e) {
            int b = to[e];

            if (b == original_parent[a]) {
                continue;
            }

            original_parent[b] = a;
            original_depth[b] = original_depth[a] + 1;
            stack.push_back(b);
        }
    }

    /*
     * 全部转为 DFS 序编号。
     *
     * parent[i] < i（根除外），这是后面单循环转移的关键。
     */
    vector<int> parent(n);
    vector<int> depth(n);
    vector<U32> degree(n);

    for (int i = 0; i < n; ++i) {
        int a = order[i];

        parent[i] = dfn[original_parent[a]];
        depth[i] = original_depth[a];
        degree[i] = static_cast<U32>(offset[a + 1] - offset[a]);

        rmq[0][i] = parent[i];
    }

    vector<int>().swap(original_parent);
    vector<int>().swap(original_depth);
    vector<int>().swap(order);
    vector<int>().swap(offset);
    vector<int>().swap(to);

    /*
     * f、g、h 分别是相邻三层的点数。
     *
     * 直接从 d = 1 开始：
     * f = 距离 0 的点数 = 1；
     * g = 距离 1 的点数 = degree。
     */
    vector<U32> buffer_a(n, 1);
    vector<U32> buffer_b = degree;
    vector<U32> buffer_c(n);

    U32* f = buffer_a.data();
    U32* g = buffer_b.data();
    U32* h = buffer_c.data();

    /*
     * count[i] = 当前距离球大小。
     *
     * lhs[i] =
     *   sum_{r <= d} (d + 1 - r) * shell_r[i]。
     *
     * lhs >= n 后，该点已经得到答案，同时 lhs 也充当 processed。
     */
    vector<U32> count(n, 1);
    vector<U32> lhs(n, 1);

    vector<U32> base_numerator(n);
    vector<U32> base_denominator(n);

    const U32 N = static_cast<U32>(n);
    int remaining = n;

    auto update_answer = [&](int i, U32 distance) {
        if (lhs[i] >= N) {
            return;
        }

        U32 current_count = count[i] + g[i];
        count[i] = current_count;

        U32 current_lhs = lhs[i] + current_count;
        lhs[i] = current_lhs;

        if (current_lhs >= N) {
            U64 numerator =
                static_cast<U64>(N)
                + static_cast<U64>(current_count) * (distance + 1)
                - current_lhs;

            U64 divisor = std::gcd(
                numerator,
                static_cast<U64>(current_count)
            );

            base_numerator[i] =
                static_cast<U32>(numerator / divisor);

            base_denominator[i] =
                static_cast<U32>(current_count / divisor);

            --remaining;
        }
    };

    /*
     * d = 1 特判。
     *
     * 此时递推式中减去的是 degree，而不是 degree - 1。
     * 因为 f[i] 恒为 1，所以直接减 g[i]（即原度数）。
     */
    update_answer(0, 1);

    h[0] = 0u - g[0];
    --degree[0];

    for (int i = 1; i < n; ++i) {
        update_answer(i, 1);

        int p = parent[i];

        /*
         * 来自父亲的贡献，同时减去回头路径。
         */
        h[i] = g[p] - g[i];

        /*
         * i 对父亲的贡献。
         * parent[i] < i，所以 h[p] 已经初始化。
         */
        h[p] += g[i];

        /*
         * 此后 degree 数组直接保存原度数 - 1。
         */
        --degree[i];
    }

    if (remaining != 0) {
        swap(f, g);
        swap(g, h);

        /*
         * d >= 2 的统一递推：
         *
         * shell_{d+1}(i)
         * = sum_{j adjacent i} shell_d(j)
         *   - (degree(i) - 1) shell_{d-1}(i)。
         *
         * 使用 uint32_t，让中间抵消过程按照模 2^32
         * 进行定义良好的运算。
         */
        for (U32 distance = 2; remaining != 0; ++distance) {
            update_answer(0, distance);

            h[0] = 0u - f[0] * degree[0];

            for (int i = 1; i < n; ++i) {
                update_answer(i, distance);

                int p = parent[i];

                h[i] = g[p] - f[i] * degree[i];
                h[p] += g[i];
            }

            if (remaining == 0) {
                break;
            }

            swap(f, g);
            swap(g, h);
        }
    }

    /*
     * 释放根号预处理中的热数组，再建立 LCA RMQ。
     */
    vector<U32>().swap(buffer_a);
    vector<U32>().swap(buffer_b);
    vector<U32>().swap(buffer_c);
    vector<U32>().swap(count);
    vector<U32>().swap(lhs);
    vector<U32>().swap(degree);

    /*
     * 将询问端点直接转为 DFS 序，后面不再需要 dfn。
     */
    for (int i = 0; i < m; ++i) {
        x[i] = dfn[x[i]];
        y[i] = dfn[y[i]];
    }

    vector<int>().swap(dfn);

    /*
     * preorder-parent RMQ。
     */
    for (int level = 1; (1 << level) <= n; ++level) {
        int half = 1 << (level - 1);
        int limit = n - (1 << level) + 1;

        const int* previous = rmq[level - 1];
        int* current = rmq[level];

        for (int i = 0; i < limit; ++i) {
            current[i] = min(
                previous[i],
                previous[i + half]
            );
        }
    }

    vector<int>().swap(parent);

    vector<pair<long long, int>> answer;
    answer.reserve(m);

    for (int i = 0; i < m; ++i) {
        int sx = x[i];
        int sy = y[i];

        int left = min(sx, sy) + 1;
        int right = max(sx, sy);

        // 题目保证 x != y，因此 length >= 1。
        unsigned length =
            static_cast<unsigned>(right - left + 1);

        int level = 31 - __builtin_clz(length);

        int lca_index = min(
            rmq[level][left],
            rmq[level][right - (1 << level) + 1]
        );

        int distance =
            depth[sx]
            + depth[sy]
            - 2 * depth[lca_index];

        if (
            static_cast<U64>(distance)
                * base_denominator[sy]
            >= base_numerator[sy]
        ) {
            answer.emplace_back(
                static_cast<long long>(base_numerator[sy]),
                static_cast<int>(base_denominator[sy])
            );
        } else {
            answer.emplace_back(distance, 1);
        }
    }

    return answer;
}

相比原代码的关键差异

根号循环由原来的：

cpp
扫描 n 个点
+ 扫描 2(n-1) 个邻接项
+ vector<bool>
+ long long 乘法

变成：

cpp
单次顺序扫描 n 个点
+ 每个点一次父亲访问
+ 两个 uint32_t 状态更新

另外还删除了：

cpp
vector<int> adj[500000]
第二次邻接表构造
vector<bool> processed
vector<long long> wsc
new_baseline
递归 DFS

我用随机树对这版与逐个终点 BFS 的暴力进行了小规模对拍；样例输出也是：

text
7 3
1 1
2 1
1 1

在当前运行环境下，合成的 $n=5\times10^5$ 链加 $m=10^6$ 询问、-O2 编译，完整计算约为 0.73 秒。不同评测机差别会很大，但这里主要是结构性降常数，不依赖 #pragma 或特定指令集。