好像主流做法是点分治，然后我在考场上写了一个时间和空间常数都很大的 tarjan+ 倍增优化建图的垃圾做法。

下面介绍我的垃圾做法：
首先考虑对于两个颜色 \(x\) ， \(y\) ，若选了颜色 \(x\) 就必须选 \(y\) ，则在图中连一条 \(x \rightarrow y\) 的边。