思路

树上dp. $dp_{i,j}$ 代表以 $i$ 为根，且 $color(i)$ 是 $red/white$ 下的最优解。转移为:

\large dp_{i,j} = \sum_{s 是 i 的儿子} dp_{s,j \oplus 1}

题目内容

曾经有一个名叫小明的年轻人，他喜欢探索和解决各种难题。有一天，他发现了一棵神奇的树。树上已经有一些点被染成了红色，另一些点被染成了白色。

但是小明想让相邻的两个点不能够颜色相同，因此他想知道最少需要进行多少次操作才能让树上所有相邻两个点的颜色不同，每次操作小明可以选择一个点改变它的染色状态（红色变白色或者白色变红色）。

请从“运行结果”或“历史提交”选择一条记录

选择提交后开始分析