本质不同的算法主要有两种：对子图大小根号分治和类启发式均摊。此外还有很多实现上的差别。
对子图大小根号分治
在线做法：
我们发现，把每个颜色的边和它们的顶点取出为一个子图，所有子图大小的和是 \(O(n)\) 级别的。那么我们就可以根号分治。
首先，要预处理每个颜色子图下的连通块。可以用并查集或 dfs 在 \(O(n)\) 或 \(O(n\log n)\) 内解决。存储需要使用 map，或者用 vector 并排序以二分查找，所以这一步的总复杂度都是 \(O(n\log n)\)。
对于 \(sz\ge \sqrt{n}\)，这样的子图不超过 \(\sqrt n\) 个，我们可以在每次询问都暴力枚举这些颜色，检测给定的两个点是否在同一个连通块。
对于 \(sz\lt \sqrt{n}\)，我们可以暴力枚举子图内所有的点对，然后用 map 存起来。这一步的复杂度是 \(n\sqrt{n}\log n\)，因为 \(\sum sz\le n\)， \(\sum (sz)^2\) 在 \(sz\) 最集中的时候取到极值。而 \(sz<\sqrt n\)，所以极值为 \(n\sqrt n\)。
每次询问的时候可以直接查找。时间复杂度 \(O(n\sqrt n\log n)\)，空间复杂度 \(O(n\sqrt{n})\)。
离线做法：
离线做法和在线最大的差别在于第二种，也就是 \(sz\lt \sqrt n\) 的部分。我们发现，在原先的做法中，我们需要把所有的 \(n\sqrt n\) 个点对的答案都存下来，然后输出的时候查找。但是现在我们可以直接在枚举的时候判断当前枚举到的点对是否是询问的点对。如果是的话，就询问并直接增加其答案，否则就不需要验证了。
离线做法的好处在于减少了空间复杂度，从 \(O(n\sqrt n)\) 变成了 \(O(n)\)，这是非常明显的优化。其次，如果不是询问对就不需要再询问了，节省了时间常数。
哈希优化：
我们可以用哈希表存储每个节点在每个颜色的连通块，同时用哈希存后面的表，可以将时间复杂度优化到 \(O(n\sqrt{n})\)，不过哈希冲突的概率还是有点大，可以配合离线优化再次优化，就会跑的更快一些。
类启发式均摊
思想是我们每次对于给定的 \(a,b\)，每个点只可能在和自己有边的颜色有贡献。考虑存储每个点相邻的所有颜色，同样是预处理每个节点在每个颜色所属的连通块。
在询问的时候，我们暴力枚举颜色，但是一定是在 \(a,b\) 中更小的集合枚举颜色，然后同时查询 \(a,b\) 是否在这个颜色属于同一个连通块。
但是这样做还是会挂的，因为我们没有均摊。我们需要给出现过的所有 \((u,v)\) 记录下来，保证每一对相同的询问我们只处理一次。这样我们的复杂度就是 \(O(n\log n\sqrt n)\)。
为什么呢？考虑如果要卡这个做法，我们怎么卡。首先，找到相邻颜色最多的 \(sqrt{n}\) 个节点，可以证明每次只在这些点中选取一定是最优的，因为如果不选它们去选别的，选回来一定会增加更小的集合的大小。
然后，考虑 \(\sqrt{n}\) 个节点，也恰好能组合 \(\sqrt{n}\) 个询问，但是这样如何询问就被我们固定下来了。第二大的贡献全部集合 \(1\) 次，第三大的贡献全部集合 \(2\) 次……第 \(\sqrt{n}\) 大的贡献 \(\sqrt{n}-1\) 次。问题就是接近选取一个有序序列，其总和为 \(n\)，贡献是 \(\sum (n-i)x_i\)。我们可以通过将大的往小的移动，比如本来是 \(x_i>x_{i-1}\)，我们把它们都设为它们的平均值，然后从大的到了小的的那部分会有更大的贡献，证明所有都相等就是最优的。
而所有的都相等，就是 \(x_i=\sqrt{n}\)，答案是 \(n\sqrt{n}\) 次贡献，每次贡献 \(\log n\)，总复杂度 \(O(n\sqrt n\log n)\)。
这个做法写的人少，复杂度证明不显然，也没有什么支线的优化。