P8916 [DMOI-R2] 暗号

考虑动规状态需要什么，很容易写出 \(f(i,0/1)\) 表达目前染色的是黑还是白。但是我们发现这样存在的问题是我们不知道子树中有多少个黑色和白色，则我们无法确定子树中各染成什么颜色。那这样我们可以考虑提前着想的思想。我们不妨假设未来这个点会被要求做贡献多少次。即 \(f(i,0/1,j,k)\) 表示未来会有 \(j\) 对连续的黑点，\(k\) 对连续的白点。那么这样就有转移 :

\[f(i,0,j,k)=\sum_{v\in S_i}\max(f(v,0,j,k+1),f(v,1,j,k))+(k+1)w_i \]

\[f(i,1,j,k)=\sum_{v\in S_i}\max(f(v,0,j,k),f(v,1,j+1,k))+(k+1)w_i \]

答案显然就是 \(\max(f(1,0,0,0),f(1,1,0,0))\)。