CF375E Red and Black Tree

看错题看成只能交换相邻节点颜色了/fn

每次操作交换两个节点颜色，可以转化为统计最终合法颜色序列相比开始，最少有多少个红点变成黑点。

可以考虑一个类似树形 dp 的过程，对于每个节点我们钦定下它会被哪个节点“笼罩”，同时由于黑点数量有限，我们还需要记录下子树内已经用了多少个黑点。

设“笼罩”节点 \(u\) 的节点为 \(f_u\)，我们不妨对 \(f_u\) 进行讨论：

• 若 \(f_u\) 位于 \(u\) 的子树 \(v\) 内，则 \(f_v\) 一定等于 \(f_u\)，否则将二者取等一定会变得不劣。此时 \(f_u\) 的贡献可以位于在 \(f_u\) 节点时记录，此时当点 \(f_u\) 为黑点时贡献为 \(0\)，否则为 \(1\)。
• 若 \(f_u\) 位于 \(u\) 的祖先，则我们可以通过不断上传使得贡献在祖先 \(f_u\) 处被记录。
• 若 \(f_u\) 既不是 \(u\) 的祖先也不在 \(u\) 子树内，我们可以通过不断上传，与 \(lca(f_u,u)\) 合并，此时 \(f_{lca(f_u,u)}\) 也一定等于 \(f_u\)，贡献同样会在 \(f_u\) 处被记录。

故我们设 \(dp_{u,i,j}\) 表示 \(u\) 子树内共用 \(i\) 个黑点，且 \(u\) 被 \(j\) 覆盖的最小代价，则当子树 \(dp_{v,p,q}\) 转移时：

• 若 \(q=j\)，\(dp_{u,i+p,j} \leftarrow dp_{v,p,q}+dp_{u,i,j}\)。

• 若 \(q\neq j\)，\(dp_{u,i+p,j}\leftarrow dp_{u,i,j}+w\)，其中 \(w\) 表示 \(\min(dp_{v,p,q})\)。需要满足 \(j\) 位于 \(v\) 子树外，\(q\) 位于 \(v\) 子树内，否则像上面说的，一定可以通过调整使其变得不劣。如此便可保证转移的复杂度为 \(O(n^3)\)。

初始 \(dp_{u,1,u}=1-a_u\)，\(dp_{u,0,v}=0\)。

需要 short 卡空间。