题目只考察连通性，不考察图更具体的结构，所以可以用 \(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\) 个字符串哈希值的复杂度。很明显，每次我们更改的字符串不能太多。
对于一次 \((d, a, b)\) 的操作，我们会修改 \(s_u\) 的第 \(d\) 个字符，其中 \(u\) 是在这次连边中被更改祖先的点数。我们要控制这个点数的量级。
所以不路径压缩，考虑按 siz 合并。这样以来，一个点在第 \(d\) 张图中，被更改祖先的次数不会超过 \(\log n\) 次（因为被更改一次祖先，它所在的并查集树大小就会翻倍），每个字符串被修改的数量不超过 \(d\log n\)，所有字符串被修改的总次数为 \(dn\log n\) 量级。
时间复杂度 \(\Theta(dn\log n)\)，常数略大。
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];
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;
--cnt[ha];
}
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;
}
如果您是从洛谷题解过来的，觉得我的题解写的不错，解决了您的疑惑的话，请回到洛谷题解区给我题解点个赞，谢谢！