洛谷 P11054
给定一张 \(n\) 个点 \(m\) 条边的无向图，每个点有一种颜色（\(0 \sim n - 1\)），还有一种颜色 \(n\)。一次操作可以让一个保留原色，或改称你想要的颜色，然后返回极大的同色连通块数量。
需要在 \(2750\) 次操作内猜出所有点的颜色。
\(n \le 250\)
首先有一个弱智的想法，对于一个点，枚举他的颜色 \(col\)，把除他以外的点都染成 \(col\)，他不变，判断返回值是否为 \(1\) 即可。于是就有了 \(n^2\) 次操作的做法，\(10pts\)
链
在链的情况下，每个点至多和两个点相邻，只需要这两个点都染成 \(col\) 即可判断。
于是可以拆成奇数位和偶数位分开做。以奇数位为例，枚举 \(col\) 将偶数位都染成 \(col\)，通过连通块个数即可判断有多少个 \(col\)。
于是就可以二分解决这个问题。（我 sb 的写分治）注意最左/右的点。
获得 \(50pts\)。
50pts
也就是找出所有的极大同色连通块，不需要求颜色。
假设最开始都不同色，慢慢进行合并。
一个一个把点加进来，即只考虑前 \(i\) 个点和他们之间的连边。合并的话就是 \(i\) 和他相邻的点，可以二分第一个和他同色的点进行 check（不详细说了，可利用附件中的 count_components 函数直接计算可以确定的查询，减少一半的操作次数）。
分析时间复杂度，已经被合并的点就不用合并了，所以如果有 \(k\) 个极大同色连通块，只会合并 \(n - k - 1\) 次，每次 \(\log n\)。并且如果已经没有和他同色了，就不要二分了，花一次操作判断，总操作次数：\((n - k) \log n + n\)
100pts
如何确定颜色，可以借鉴链的做法。
链的做法是对于每个点，都有 \(1/2\) 个点颜色为 \(col\) 的点和他相邻，这样他是否为 \(col\) 会有显现出来。
类似的的，我们对图进行分层，其实就是搜出一颗生成树，按深度分层。对于奇数层、偶数层分开做。以奇数层为例，把所有偶数层的染成 \(col\)，每次二分奇数层中第一个为 \(col\) 的点，看查询结果和全不是 \(col\) 的结果（count_components 函数）是否一致即可。
你或许会问，那为什么要找出极大同色连通块？
因为如果不这样，奇数点连边可能会同色，就区分下面这种情况了。
只有 \(k\) 个连通块，确定一个连通块的颜色花费 \(\log n\) 次操作，每种颜色多花费两次操作（奇数层、偶数层各需要一次）来判断是否还有这种颜色的连通块（否则可能 \(2\) 个 \(\log\) ）
总共 \(n \log n + 3n\)，刚好卡过，实现细节一点。