「SegTree」と「任意の２頂点の距離を高速に求めるデータ構造」を用意します（LCA + DFSなど）
計算量はこの２頂点間の距離を \(O(1)\) で求められるものとしています。（ \(O(\log(N))\) かかるのであれば、\(\log(N)\) 倍になります。）

色ごとにSegTreeをつくり、各nodeでは以下を管理します。

ある頂点集合 \(S\) について
・最も遠い頂点対（複数ある場合はいずれか一対） \(u_S, v_S\) とその距離 \(d_S\)

ある２つの頂点集合 \(X, Y\) について、そのmergeは上の情報から可能です。なぜなら、merge後の頂点集合における、最も遠い頂点対のひとつに \(u_X, v_X, u_Y, v_Y\) のうち２つから構成されるものが存在するからです。

よって、いまその色が塗られている頂点についてのみをactiveにすることで、SegTreeに乗せることができます。（いま塗られていないなら単位元にするなどでよいです）

色ごとのSegTreeは、「その色になることがある頂点」のみを管理すれば良く、これは合計で空間 \(O(N + Q)\) です。
クエリを先読みし必要な長さだけ構築し、適切に更新することで問題全体を \(O((N+Q)\log(N+Q))\) で解くことができます。