Uoj#510 【JOISC2020】首都

题意：给出一棵 个节点的树，点已染色。

对于一种染色方案，如果有某种颜色形成恰好一个树上联通块，则称这种染色方案是好的。

可以将颜色 统一变为颜色 或 ，这称作一次合并操作。

至少要进行多少次合并操作，才能得到好的染色方案。

，时限 。

---

不妨假设我们最后要选择颜色 形成恰好一个树上联通块。

那么，首先要把 内部打通，于是需要把点集 在树上的虚树路径都同化为 。

但是，由于同化了其他的颜色，又可能出现不连续的情况。

我们由此受到启发，若颜色 有某个点在颜色 的路径上，说明若想选 ， 必须合并。

对此，我们连边 ,然后缩强连通分量。

现在，若选择颜色 ，则要把 的后继连通分量里面的颜色全都合并。

显然，选择没有出度的连通分量最优，答案就是所有无出度连通分量大小的最小值 。

---

连边可以使用 树剖 + 线段树 优化，这样点数是 的，边数是 的，很不平衡。

可以使用倍增优化，对于每个点 ，预处理点 同时连向 向上的 个点。

这样就能做到 点数， 边数了。复杂度