雅礼NOIP2018集训 day3 w
题面
有一棵n个节点的树，每条边长度为1，颜色为黑或白。 可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。 对于某些边，要求在操作结束时为某一种颜色。 给定每条边的初始颜色，求最小操作数，以及满足操作数最小时，最小的操作路径长度和。
数据范围
有梯度，所有数据\(n\leq 10^5\)
题解
我们可以把边重新分一下类:任意边(即目标状态是任意的边)、异边(即原状态与目标状态相反的边)，同边(即原状态与目标状态相同的边)
经过分析最优解是不会走同边的，因为走了同边会花费更多的操作数或操作路径长度来复原，而任意边可走可不走。
而图的操作数即是图上所有要走的边给点算度，奇数度的点的一半即是图的操作数
因此我们可以进行树形DP求解，注意每个点要分两类讨论，与儿子点要走的边的个数的奇偶性
标签：操作数,路径,day3,NOIP2018,雅礼,集训 From： https://www.cnblogs.com/blln/p/16596760.html