CF734E 思维

· · 个人记录

我们将相同颜色的连通块缩为一点。

然后我们在后来的树中找一个点并从它开始向外拓展。

我们先把它的颜色取一个反，这时距离它为 1 的点就满足了条件（因为和它颜色相同的点会跟着一起改，颜色不同的点在改完后颜色相同）。

再取一个反，距离它为 2 的点也满足了条件。

以此类推。答案即为这棵树的直径除以 2，然后上取整。

然后你并不需要求出这棵新树，只需要将原树两端异色的边设置权为 1，同色为 0，跑带权直径即可