欢迎您到我的博客查看本文，谢谢！

题目只考察连通性，不考察图更具体的结构，所以可以用 $d$ 个并查集维护。

两个点 $u$ 和 $v$ 在图 $i$ 上连通，当且仅当图 $i$ 上 $u$ 和 $v$ 的并查集祖先相同。

因此，两个点 $u$ 和 $v$ 在 $d$ 张图上都连通，等价于对于任意 $i$，$u$ 和 $v$ 在第 $i$ 张图的并查集祖先相同。

所以考虑对每个点 $u$ 维护一个长度为 $d$ 的字符串 $s_u$，$s_u(i)$ 表示第 $i$ 张图上 $u$ 的并查集祖先。

于是 $u$ 和 $v$ 在 $d$ 张图上连通等价于 $s_u = s_v$。

我们动态地维护这 $n$ 个字符串的哈希值，对于哈希值相同的 $k$ 个字符串，可以给答案贡献 $k^2$。开桶记录即可。

因为桶的下标是字符串哈希值域量级，桶用 unordered_map（如果会哈希表用哈希表也行）。

现在考虑动态维护 $n$ 个字符串哈希值的复杂度。很明显，每次我们更改的字符串不能太多。

对于一次在第 $k$ 张图连接 $a$ 和 $b$ 的操作，我们会修改 $s_u$ 的第 $k$ 个字符，其中 $u$ 是所有这次连边中在并查集上被更改祖先的点。我们要控制这个点数的量级。

所以不路径压缩，考虑按并查集树的大小启发式合并。这样以来，一个点在第 $d$ 张图中，被更改祖先的次数不会超过 $\log n$ 次（因为被更改一次祖先，它所在的并查集树的大小就会翻倍），每个字符串被修改的数量不超过 $d\log n$，所有字符串被修改的总次数为 $dn\log n$ 量级。

时间复杂度 $\Theta(dn\log n)$，常数略大。

另外这里所有字符串长度都是 $d$，所以可以不用写普通的字符串哈希，直接给每个位置随机一个权值 $w(i)$，记 $S(i)$ 为字符串 $S$ 的第 $i$ 个字符，我们令 $S$ 的哈希值为 $\sum w(i) \times S(i)$ 即可。这样代码会更好写，而且规避了可能的卡哈希问题（本题好像把基数为 131 的自然溢出哈希卡了）。

typedef unsigned long long ull;

const int D = 205;
const int N = (int)5e3 + 5;

int rt[D][N];
std :: vector <int> t[D][N]; // t[k][u] 表示第 k 层图中以 u 为根的并查集树
ull ha[N], val[D];
int ans;
std :: unordered_map <ull, int> cnt;

inline void add(ull ha) {
	int x = cnt[ha];
	ans += 2 * x + 1;
	++cnt[ha];
}

inline void del(ull ha) {
	int x = cnt[ha];
	ans -= 2 * x - 1;
	if (--cnt[ha] == 0)
    	cnt.erase(ha); // 本题一个哈希值消失就很难再现，直接 erase 掉能显著减小常数。不 erase 也没什么问题。
}

int main() {
	int d = read(), n = read(), m = read();
	std :: mt19937_64 rng(std :: random_device{}());
	for (int i = 1; i <= d; ++i)
		val[i] = rng();
	for (int i = 1; i <= d; ++i) {
		for (int u = 1; u <= n; ++u) {
			rt[i][u] = u;
			ha[u] += u * val[i];
			t[i][u].push_back(u);
		}
	}

	for (int u = 1; u <= n; ++u)
		add(ha[u]);
	
	while (m--) {
		int u = read(), v = read(), k = read();
		u = rt[k][u]; v = rt[k][v];
		if (u == v) {
			printf("%d\n", ans);
			continue;
		}
		if (t[k][v].size() > t[k][u].size())
			std :: swap(u, v);
		for (int x : t[k][v]) {
			t[k][u].push_back(x);
			rt[k][x] = u;
			del(ha[x]);
			ha[x] += (u - v) * val[k];
			add(ha[x]);
		}
		t[k][v].clear();
		printf("%d\n", ans);
	}
	return 0;
}

如果您觉得我的题解写的不错，解决了您的疑惑的话，请给我题解点个赞，谢谢！

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

typedef unsigned long long ull;

const int D = 205;
const int N = (int)5e3 + 5;

int rt[D][N];                    // rt[k][u]: 第k层中u的并查集根
vector<int> t[D][N];             // t[k][u]: 第k层以u为根的集合元素列表
ull ha[N], val[D];               // ha[u]: u的哈希值; val[i]: 第i层的随机权重
int ans;                         // 当前答案
unordered_map<ull, int> cnt;     // 统计每个哈希值出现次数

// 快读函数（根据题目需要保留）
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + (ch ^ 48); ch = getchar(); }
    return x * f;
}

// 添加一个哈希值：新增元素与原有x个相同哈希的元素配对，贡献2x+1
inline void add(ull h) {
    int x = cnt[h];
    ans += 2 * x + 1;
    ++cnt[h];
}

// 删除一个哈希值：移除元素会减少与剩余x-1个元素的配对，损失2x-1
inline void del(ull h) {
    int x = cnt[h];
    ans -= 2 * x - 1;
    if (--cnt[h] == 0) cnt.erase(h);  // 及时清理，减小常数
}

int main() {
    int d = read(), n = read(), m = read();
    mt19937_64 rng(random_device{}());
    
    // 为每层生成随机权重
    for (int i = 1; i <= d; ++i) val[i] = rng();
    
    // 初始化：每个点独立成集合
    for (int i = 1; i <= d; ++i) {
        for (int u = 1; u <= n; ++u) {
            rt[i][u] = u;
            ha[u] += (ull)u * val[i];  // 初始哈希 = Σ(点编号×层权重)
            t[i][u].push_back(u);
        }
    }

    // 初始所有点的哈希加入统计
    for (int u = 1; u <= n; ++u) add(ha[u]);
    
    // 处理m次操作
    while (m--) {
        int u = read(), v = read(), k = read();
        u = rt[k][u]; v = rt[k][v];  // 找到在第k层的实际根
        
        if (u == v) {  // 已在同一集合，答案不变
            printf("%d\n", ans);
            continue;
        }
        
        // 启发式合并：小集合合并到大集合
        if (t[k][v].size() > t[k][u].size()) swap(u, v);
        
        // 遍历小集合v中的所有点，合并到u
        for (int x : t[k][v]) {
            t[k][u].push_back(x);    // 加入大集合
            rt[k][x] = u;            // 更新并查集父节点
            del(ha[x]);              // 先删除旧哈希
            
            // 🔧 关键修复：正确处理 (u-v)*val[k] 的符号问题
            if (u >= v) {
                ha[x] += (ull)(u - v) * val[k];
            } else {
                ha[x] -= (ull)(v - u) * val[k];  // ull减法自动模2^64
            }
            
            add(ha[x]);              // 添加新哈希
        }
        t[k][v].clear();  // 清空已合并的集合
        printf("%d\n", ans);
    }
    return 0;
}