因为处理玩完一颗子树后,它要么是颜色都相同(显然不用再管它了)
要么显然是留到它的父亲,留一条路径延伸过来。
那么显然就是子树中存在一条到根的路径。
使得这条路径上的点与其他点不同。
那么我们设计三位DP
设f[u][0/1][0/1]
表示u这颗子树它最终变为了哪种颜色且是否留了路径
那么我们考虑第三维是0的情况:
若如果我们最终要变成与根节点相同的颜色。
f[u][c][0] = f[l][c][0] + f[r][c][0]
f[l][c^1][1]