尽管我们知道，不带按秩合并但带路径压缩的并查集的最坏时间复杂度是单次 $\mathcal{O}(\log n)$，但是姚期智教授证明了，在平均情况下为单次 $\mathcal{O}(\alpha(n))$。

所以如果以平均状况来算的话，你的代码时间复杂度应该是 $\mathcal{O}(n^{3/2}\alpha(n)+V)$，其中 $V=10^7$。

而 TLE 的原因是，在其中加入了一些奇怪操作，比如快速幂。那么这个 $\log$ 虽然在最坏情况下，可以和并查集的复杂度合并，但在平均情况下却成为了复杂度瓶颈，最终导致 TLE。

所以一个比较好的尝试就是，在其中使用快速幂的时候，注意到底数不超过 $10^5$，指数不超过 $\sqrt{10^5}=10^{2.5}$，直接预处理出来。

示例：

Original:
int lar = dus.large[dus.find(xid)];
sum[i] += lar * (y - x);
prod[i] = 1ll * prod[i] * ksm(1ll * js[x] * invjs[y] % mod, lar) % mod;
// js 表示阶乘，invjs 表示阶乘的逆元
// TLE

New:
prod[i] = 1ll * prod[i] * jsmi[lar][x] % mod * invjsmi[lar][y] % mod;
-----
for (int i = 0; i < N; ++ i)
{
    jsmi[0][i] = invjsmi[0][i] = 1;
    for (int j = 1; j < S; ++ j)
        jsmi[j][i] = 1ll * jsmi[j - 1][i] * js[i] % mod,
        invjsmi[j][i] = 1ll * invjsmi[j - 1][i] * invjs[i] % mod;
}

从而优化代码的平均复杂度，进而得以通过本题。