我写的做法应该是 $n \log n +q \log n$ 的在线做法/xk。提一点建议吧。

首先你要尽可能确保你的实现精细些。

• 不要用 pbds 和 map，用 umap 的效率会提升。
• 使用尽可能快的IO方式。
• 减少umap开的个数，事实上，大部分的都能用 vector 去代替，以及使用 .count 函数，避免开无意义的节点。
• 使用链式前向星存图。
• 有用的颜色对只有 $n-1$ 个，所以在询问的时候要先判掉无用的，不要上来就查。
• 在第一次合并相邻的颜色相同的点的时候，先判断 a[v]!=col。
• 耐心多提交几次，这可能需要一定的提交次数。