ARC097D Monochrome Cat

题意：给出一棵 个点的树，初始时每个点为黑色或白色。

以任意节点开始操作，每轮操作可以选择是否移动到相邻节点，然后将当前所在的节点颜色取反。

求使所有点变为黑色的最小操作次数。

，时限 。

---

首先，显然只用保留全体白色点的虚树。

然后，必须要将这颗树完整遍历一次，但经过每个点的次数随着起止点的选取而变化，不便分析。

不妨先考虑回路，这样，每条边都会被正反各走一次，每个点都恰会被经过度数次。

这样走过之后，标记树上剩余的白点，只需要在此处停留一步就能将其变为黑点。

回路的问题已经解决了，现在考虑起止点的选择。假设选择 ，那么可以让 中所有点少经过一次。

• 对于没有标记的点，少经过一次，所以需要停留一回合，没有贡献。

• 对于有标记的点，少经过一次，所以不需要再停留，贡献为 。

所以，选择一条标记点最多的路径即可。

注意， 是不包含在路径内的，所以需要特判只有一个白点的情况。

只要有多个白点，叶节点处的白点肯定不是标记点，选出的路径必然可以以两个无标记叶节点为端点。这样，端点在不在路径内就无关紧要了。

最终答案为 虚树边数 标记点数 路径最大标记点数。

复杂度 。